Now that we’ve learnt about weighted graphs and single-source shortest-path algorithms like Dijkstra and Bellman Ford, it’s time to implement them. You can work in any programming language of your choice - Python, C++, Java, or anything else you want. Let’s get started!

Problem Statement

You are given an undirected weighted graph with $n$ nodes and $m$ edges. The nodes are numbered from $0$ to $n-1$. Find the shortest distance from the source (node $0$) to all other nodes. If there is no path from the source to a particular node, output INF instead (for infinity).

Constraints: $n \leq 10^5$ and $m \leq 10^6$.

IO description

Input description: The input file contains multiple test cases. Each test case begins with “Test case: X”. This is followed by a line which has two numbers, $n$ (the number of nodes) and $m$ (the number of edges). The next $m$ each contain 3 numbers $u$, $v$ and $w$, denoting that there is an edge $(u, v)$ with weight $w$.

Sample input:

Test case: 1
3 1
1 2 4
Test case: 2
3 1
0 1 6
Test case: 3
3 3
0 1 7
2 1 3
0 2 13
Test case: 4
5 7
2 0 107
1 0 539
4 3 11
0 3 435
0 4 85
3 1 1
1 4 58
Test case: 5
8 16
7 2 2
3 7 3
0 4 365
1 4 1
6 4 50
3 5 14
3 2 40
1 0 3
6 1 426
2 4 145
3 1 1
0 3 12
5 0 117
1 2 596
0 7 201
5 4 189

Output description: Output should contain one line per test case. The line should have $n$ numbers, where the $i$th number = $d(0, i)$ = distance between node $0$ and node $i$. If there is no path from the source to a particular vertex, output INF instead (for infinity).

Sample output:

0 INF INF
0 6 INF
0 7 10
0 97 107 96 85
0 3 9 4 4 18 54 7

In the first test case, there is no edge from node $0$. Hence, the distance to node $1$ and node $2$ is infinity.

In the second test case, there is a direct edge from node $0$ to node $1$ with weight $6$.

In the third test case, there is a direct edge between every pair of nodes, but the path from node $0$ to node $1$ to node $2$ is cheaper than the direct edge between node $0$ and node $2$.

Note that the distance from the source to itself is always 0.

Notes

1. Start by creating an adjacency list from input. Make sure to add edges in both directions.
2. For implementing Djikstra’s algorithm, you don’t need to implement your own heap or priority queue. Most languages have a pre-implemented one.

Grading your solution

You’ll find all the files required to check your solution here: Dijkstra’s algorithm. In particular, the folder includes 3 files - input, answer and grader.py.

Do the following to check your solution.

{COMMAND TO RUN C++/JAVA/PYTHON CODE} < input > output 
python grader.py output answer

Solution

The solution for this assignment can be found here: dijkstra.py. The code takes about 8 seconds to run for all test cases combined. Note that if you implemented the solution in C++ / Java, your code should be executing about > 5x faster.