CODEWITHSUNDEEP
algorithmgraphtheory
user1799323
user1799323

Reputation: 659

Dijkstras Algorithm - Parent Nodes?

My professor wants us to implement it for a single source node to all other nodes in the network. He said to keep track of the shortest path by using parent nodes, but I have no idea what this means in the context of the algorithm.

I can implement my code more or less properly, in the sense that my output distances are all correct for any network I run it on.

But most online resources talk about visiting nodes and marking them as visited once you explore all of the neighboring nodes. So for instance, if nodes A and B neighbor node C, and the new distance to A is smaller than that of B, do I mark node C visited? And then what happens if I get to node A and realize that the path it leads me down would actually cause an already recorded distance to actually be larger?

Upvotes: 0

Views: 1843

Answers (2)

Jasper
Jasper

Reputation: 11908

My professor wants us to implement it for a single source node to all other nodes in the network. He said to keep track of the shortest path by using parent nodes, but I have no idea what this means in the context of the algorithm.

Well, that just mean that for each node, you store which node is the node it came from in the shortest path to it. This way, you can walk the shortest path in reverse order once you're done with your algorithm to not only find the distance of the shortest path, but also the shortest path itself.

But most online resources talk about visiting nodes and marking them as visited once you explore all of the neighboring nodes.

You mark a node visited after it was the unvisited node with the lowest distance. Unless there are negative distances, you won't be able to find a path that has a lower distance (and even then, it's only a problem if your graph has a cycle with distance below zero).

Upvotes: 1

Mel Nicholson
Mel Nicholson

Reputation: 3225

In order to get a path (as opposed to just a cost) from Dystra's algo, instead of saving a best-cost for each node, save the pair (best_cost, from_where). The from-where is a handle to the adjacent node that produced the best_cost.

You can then follow the from_where pointers all the way back to the origin to get the best path. I suspect "parent" is his name for the from_where element in the 2-tuple/pair.

Upvotes: 2

Related Questions