Discussion on: Completed JavaScript Data Structure Course, and Here is What I Learned About Graph (+ Dijkstra Algorithm).

[peter staal]

Thanks! Having trouble with this part:

while (prev[current]) {
                    result.push(current);
                    current = prev[current];
                }
                break;

Could you explain it step by step?

[peter staal]

Maybe if you could explain what the final prev list looks like?

[Maiko Miyazaki]

Hi Peter, thanks for the question!
If we run Dijkstras("Dublin", "AliceSprings"),
the final prev list should look like:

AbuDhabi: "Dublin"
AliceSprings: "Sydney"
Brisbane: "AbuDhabi"
Doha: "Dublin"
Dubai: "Dublin"
Dublin: null
HongKong: "Dublin"
Melbourne: "AbuDhabi"
Perth: "Dubai"
Sydney: "HongKong"

This list shows where you visited previously to get to each location. i.e. You came from HongKong to get to Sydney..

If current="AliceSprings",

while (prev[current]) {
                    // push "AliceSprings" in result list
                    result.push(current);
                    // current will be "Sydney" with this line
                    current = prev[current];
                    // continue until current="Dublin"
                }
                break;

Hope it helps! :)