Shortest Path on a Weighted Graph


Collapse Content

The Weighted graphs challenge demonstrated the use a Breadth-First-Search (BFS) to find the shortest path to a node by number of connections, but not by distance. When driving to a destination, you'll usually care about the actual distance between nodes. What algorithm will find the shortest total distance to each node?

Shortest Path Algorithm

BFS makes sure to always reach the points in order of distance, so every node it reaches is along the shortest path. How can you make sure to do the same on a weighted graph? Think about an algorithm you could use before clicking below.

Dijkstra's algorithm

Dijkstra Animation
You can view Dijkstra's algorithm in action here. Enter a 0 and click the button to run Dijkstra from node 0. See also Example Networks1 for a walk-through of the algorithm.

Challenge

Given a graph of input in the adjacency matrix format, can you find and print the distance from node 0 to all the nodes?

Sample Input

1
6
0 0 1 3 0 0
0 0 0 5 0 0 
1 0 0 2 1 4
3 5 2 0 7 0
0 0 1 7 0 2
0 0 4 0 2 0

Sample Output

0 8 1 3 2 4 

Explanation

Weighted Graph

The output is the shortest distance to each node in order, as shown in the middle column in the following table:

node distance path
0 0 0
1 8 0->2->3->1
2 1 0->2
3 3 0->2->3
4 2 0->2->4
5 4 0->2->4->5

Challenge

Print out the shortest (weighted) distance from Node 0 to all the other nodes.

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Comments

  • Note that priority queue won't return highest priority item if it isn't updated as distances are updated.

Contact Us