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