# Hands-on: Implementing Dijkstra's algorithm

July 04, 2018

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

- Start by creating an adjacency list from input. Make sure to add edges in both directions.
- 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.