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

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