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

×

Dijkstra's Algo

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

shubhgoyal5's gravatar image

0★shubhgoyal5
56621
accept rate: 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);
link

answered 08 Apr '15, 22:24

bogdanboboc97's gravatar image

2★bogdanboboc97
161
accept rate: 0%

edited 08 Apr '15, 22:47

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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