Dijkstra

• Input:
• directed or undirected weighted graph with N nodes and M edges
• source node
• Output:
• array distance of length N, where:
• distance[i] - the shortest distance from source node to node i if i is reachable
• distance[i] = $\infty$ otherwise
• Time complexity: $O(N^2 + M)$

Description

Initialization

Set distance[source_node] = 0, and for all other nodes v set distance[v] = -1. Boolean array relaxed stores for each node v whether it's already relaxed. Initially all nodes are unrelaxed.

Relaxation

The Dijkstra's algorithm runs for N iterations. At each iteration a node u is chosen as unrelaxed node which has the least value distance[u]. Next, from node u relaxations are performed: all edges of the form (u, w, v) are considered, and for each node v the algorithm tries to improve the value distance[v] by applying distance[v] = min(distance[v], distance[u] + w).

Relaxation

After all such edges are considered, the current iteration ends and node u marked as relaxed. Finally, after N iterations, all nodes will be marked, and the algorithm terminates. We claim that the found values distance[v] are the lengths of shortest paths from source_node to all nodes v.

Example

Let's see how the Dijkstra algorithm works with an example. We use an undirected graph with 7 nodes.

We start from node 1. The Dijkstra algorithm starts by setting distance[1] = 0 and for any other node v: distance[v] = -1.

Dijkstra algorithm found unrelaxed node with least distance value - node 1 and perform relaxations along all its edges. It set distance[2] = 1, distance[3] = 2 and mark node 1 as relaxed.

Next node is node 2. Dijkstra algorithm set distance[4] = 3, distance[5] = 4 and mark node 2 as relaxed.

Next node is node 3. Dijkstra algorithm set distance[6] = 3 and mark node 3 as relaxed.

Next node is node 4. Dijkstra algorithm did not update any distance and just mark node 4 as relaxed.

Next node is node 6. Dijkstra algorithm set distance[7] = 4 and mark node 6 as relaxed.

Next node is node 5. Dijkstra algorithm did not update any distance and just mark node 5 as relaxed.

Next and last node is node 7. Dijkstra algorithm did not update any distance and just mark node 7 as relaxed. Dijkstra algorithm is finished.

Code

                        def dijkstra(
                            graph: Dict[int, List[Tuple[int, int]]],
                            source_node: int,
                        ) -> List[int]:
                            n = len(graph)
                            distance = [-1] * n
                            relaxed = [False] * n
                        
                            distance[source_node] = 0
                            for i in range(n):
                                u = -1
                                for j in range(n):
                                    if relaxed[j] == False and (
                                        u == -1 or (distance[j] != -1 and distance[j] < distance[u])
                                    ):
                                        u = j
                                if u == -1:
                                    break
                                for v, w in graph[u]:
                                    if distance[v] == -1 or distance[v] > distance[u] + w:
                                        distance[v] = distance[u] + w
                                relaxed[u] = True
                        
                            return distance