Dijkstra's Algo

dijkstra
graph
graph-theory

#1

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??


#2

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);