You are not logged in. Please login at www.codechef.com to post your questions!

×

# Dijkstra's Algo

 0 I know how to find the shortest path between two given nodes. However, I don't know how to find the nodes that actually contain that shortest path apart from those two given nodes. (as the case maybe) For example, if I have to find the shortest path b/w nodes 1 and 8 in a total of 8 given nodes, the shortest path contains the following nodes: 1, 4, 5, 7, 8 (for instance). So my question is: How do I find 4, 5 and 7 precisely?? asked 08 Apr '15, 21:08 56●6●21 accept rate: 0%

 0 void dijkstra(int start) { dist[start]=0; pre[start]=0; heap_insert(x); while(!heap_empty()) { int x=heap_top(); heap_pop(); for(auto y: graph[x])//for each neighbor of node x if(dist[x] + cost[x][y] < dist[y])//if distance from node start to node x + the cost of edge x-y is lower than distance from start to y { dist[y]=d[x] + cost[x][y]; pre[y]=x;//you have reached node y from x heap_insert(y); } } }  and now for(int node=y;node!=0;node=pre[node]) (use node);  answered 08 Apr '15, 22:24 16●1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,236
×195
×180

question asked: 08 Apr '15, 21:08

question was seen: 1,222 times

last updated: 08 Apr '15, 22:47