Dijkstra’s Algorithm

Our goal is to find the length of the shortest path to reach each node from the given start node.

• Use DP (Dynamic Programming) table to record and update the shortest path and its length.

Key Idea

1. Examine outgoing edges from the start node, visit the nearest node.
   • For example, start = A, nearest = C
2. Greedy selection.
   Examine outgoing edges from that nearest node.
   Compare the original path and the new path via that nearest node.
   Update to the new path when it is shorter.
   • For example, from C we can reach B.
   • The original path to reach B from the start node A is (A, B) with length 4.
   • The new path to reach B via C from the start node A is (A, C, B) with length 2+1=3.
   • Since the new path is shorter, update to this new path.
3. Repeat 1 and 2 until all nodes are visited.

Process

1. Initialize the DP table:
   • d = [inf, inf, inf, inf, inf], distances from A to A, B, C, D, E. (inf represents infinity.)
   • p = [[], [], [], [], []], paths from A to A, B, C, D, E.
   • v = [False, False, False, False, False], check True if visited.
2. Set the start node as A. Update to 0 and (A, A) to the corresponding positions. Examine the edges leaving from A. We can reach B, C.
   • d = [0, 4, 2, inf, inf]
   • p = [[(A, A)], [(A, B)], [(A, C)], [], []]
   • v = [True, False, False, False, False]
   • Move to C, which has the shortest edge leaving from A.
3. Examine the edges leaving from C. We can reach B, D, E.
   • For B, original path vs new path via C: len(A, B) = 4, len(A, C, B) = 2 + 1 = 3. Update to the new path (A, C, B) and its length 3.
   • For D, original path vs new path via C: len(A, D) = inf, len(A, C, D) = 2 + 4 = 6. Update to the new path (A, C, D) and its length 6.
   • For E, original path vs new path via C: len(A, E) = inf, len(A, C, E) = 2 + 5 = 7. Update to the new path (A, C, E) and its length 7.
   • d = [0, 3, 2, 6, 7]
   • p = [[(A, A)], [(A, C, B)], [(A, C)], [(A, C, D)], [(A, C, E)]]
   • v = [True, False, True, False, False]
   • Move to B, which has the shortest edge leaving from C.
4. Examine the edges leaving from B. We can reach C, D, E.
   • For C, original path vs new path via B: len(A, C) = 2, len(A, C, B, C) = 3 + 1 = 4. Preserve the original path (A, C) and continue.
   • For D, original path vs new path via B: len(A, C, D) = 6, len(A, C, B, D) = 3 + 2 = 5. Update to the new path (A, C, B, D) and its length 5.
   • For E, original path vs new path via B: len(A, C, E) = 7, len(A, C, B, E) = 3 + 3 = 6. Update to the new path (A, C, B, E) and its length 6.
   • d = [0, 3, 2, 5, 6]
   • p = [[(A, A)], [(A, C, B)], [(A, C)], [(A, C, B, D)], [(A, C, B, E)]]
   • v = [True, True, True, False, False]
   • Move to D, which has the shortest edge leaving from B.
5. Examine the edges leaving from D. We can reach nothing.
   • d = [0, 3, 2, 5, 6]
   • p = [[(A, A)], [(A, C, B)], [(A, C)], [(A, C, B, D)], [(A, C, B, E)]]
   • v = [True, True, True, True, False]
   • Move to E, which is unvisited.
6. Examine the edges leaving from E. We can reach D.
   • For D, original path vs new path via E: len(A, C, B, D) = 5, len(A, C, B, E, D) = 6 + 1 = 7. Preserve the original path (A, C, B, D) and continue.
   • d = [0, 3, 2, 5, 6]
   • p = [[(A, A)], [(A, C, B)], [(A, C)], [(A, C, B, D)], [(A, C, B, E)]]
   • v = [True, True, True, True, True]
   • Since all nodes have been visited, the process is complete.
7. The final d and p is our answer.

Code

The nodes A, B, C, D, E correspond to the nodes 1, 2, 3, 4, 5 respectively.

Since the index is start from 0, we need a space for node 0 although it is not used.

INF = int(1e9)
n, m = 5, 9 # Number of nodes and edges
graph = [
    # graph[x].append((y, z)): edge from x to y, with weight z
    [], # Edges from 0 (unused)
    [(2, 4), (3, 2)], # Edges from 1
    [(3, 3), (4, 2), (5, 3)], # Edges from 2
    [(2, 1), (4, 4), (5, 5)], # Edges from 3
    [], # Edges from 4 (has no outgoing edges)
    [(4, 1)] # Edges from 5
]
distances = [INF] * (n + 1)
visited = [False] * (n + 1)
start = 1

def nearest_node():
    min_value = INF
    index = 0
    for i in range(1, n + 1):
        if distances[i] < min_value and not visited[i]:
            min_value = distances[i]
            index = i
    return index

def dijkstra(start):
    distances[start] = 0
    visited[start] = True
    for j in graph[start]:
        distances[j[0]] = j[1]
    for _ in range(n - 1):
        current_node = nearest_node()
        visited[current_node] = True
        for j in graph[current_node]:
            cost = distances[current_node] + j[1]
            if cost < distances[j[0]]:
                distances[j[0]] = cost

dijkstra(start)
for i in range(1, n + 1):
    if distances[i] == INF:
        distances[i] == 'INF'
print(distances[1:])