Home > Mobile >  Display nodes from the shortest path between two nodes
Display nodes from the shortest path between two nodes

Time:03-21

Let's say that we use Dijkstra algorithm and now we know the shortest distance between source node and every node from the graph. What should I do to know which nodes was visited for every distance?

CodePudding user response:

Whenever you find a shorter path to a node, and therefore decrease its distance, you should also record the node's predecessor. That's the node who's edge list you are enumerating when you discover the new distance.

When you're done, you can then backtrack from any node through the chain of predecessors to find all the nodes on the shortest path to it.

  • Related