Dijekstra Algorithm Undirected graph
Hello! How would I evaluate the shorted path in the Graph by seeing the table below the graph?
Graph link:
https://ibb.co/Kqv8rmJ
Graph link:
https://ibb.co/Kqv8rmJ
each cell shows the total cost and the previous node of the path
so you go backwards using the previous node to reconstruct the path
G = 18,F (path F->G)
F = 9, C (path C->F->G)
C = 3,A (path A->C->F->G)
so you go backwards using the previous node to reconstruct the path
G = 18,F (path F->G)
F = 9, C (path C->F->G)
C = 3,A (path A->C->F->G)
Can you also please explain to me about this one too. The previous table was diagonal but this one is confusing.
https://ibb.co/dp6jM0H
Thanks!
https://ibb.co/dp6jM0H
Thanks!
It's irrelevant whether it is diagonal. Which point would you like to end up at? You go backwards from that point from the cell in which it was finalised (here, the last entry in that column), just as @ne555 showed in the previous example.
You would also learn Dijkstra's algorithm if you followed the "rounds" in the table. Personally, I would indicate in that table when a node had been finalised; e.g. by making it bold, or shading out everything below it.
You would also learn Dijkstra's algorithm if you followed the "rounds" in the table. Personally, I would indicate in that table when a node had been finalised; e.g. by making it bold, or shading out everything below it.
Last edited on
Topic archived. No new replies allowed.