Chapter 5 - Shortest Path

Floyd and Dijkstra all use BFS, not DFS

Why? These algorithms use the same approach, at any time it keeps a best_so_far(u,w) array which stores the shortest path from u to w, and then it keeps finding another entry and combine two edges that might be shorter than the current best so far.

if best_so_far[u,w] > best_so_far[u,r] + best_so_far[r,w]:
    best_so_far[u,w] = best_so_far[u,r] + best_so_far[r,w]

Floyd-Warshall algorithm for shortest path

def floyd_warshall(n, edge_cost):
    # Initialize the path cost matrix with edge costs
    path_cost = [[float('inf')] * n for _ in range(n)]
    # Initialize the intermediate matrix with -1 (no intermediate nodes)
    intermediate = [[-1] * n for _ in range(n)]

    # Set initial path costs and intermediate nodes based on edge_costs
    for i in range(n):
        for j in range(n):
            if i == j:
                path_cost[i][j] = 0  # Cost to itself is 0
            elif edge_cost[i][j] != float('inf'):
                path_cost[i][j] = edge_cost[i][j]
                intermediate[i][j] = i  # Set intermediate to i if there's a direct edge

    # Floyd-Warshall algorithm to find shortest paths
    for k in range(n): # this loop iterates over each vertex k as a potential intermediate
        for i in range(n): # this loop iterates over each vertex i as starting point
            for j in range(n): # this loop iterates over each vertex j as ending point
                # If a shorter path from i to j through k is found
                if path_cost[i][j] > path_cost[i][k] + path_cost[k][j]:
                    path_cost[i][j] = path_cost[i][k] + path_cost[k][j]
                    intermediate[i][j] = k

    return path_cost, intermediate

Why do we need k or why do we need intermediate at all?

Suppose we have 3 vertices A B and C, A -> B -> C is 6, and A->C is 10, innately we will choose the first path because it is shorted than the latter, however, when we are reconstructing the graph/path the program has no knowledge about it. The program will only know the shortest path from A to C is 6, but when we try to print the shortest path, it will have no knowledge that it goes from A to C by passing B.

In short, the index of 3 loops matter, the outer loop must be latesest intermediate node and the inner loops must sequence over all departure and arrival node

Print the actual shortest path

def full_path_driver(i, j):
    """
    Driver function to print the shortest path from vertex i to vertex j.
    """
    if kIntermediate[i][j] != -1:  # There is a path from i to j
        list_path(i, j)
        print(j)  # Print the last vertex j
    else:
        print(f"No path from {i} to {j}")

def list_path(i, j):
    """
    Recursive function to print vertices on the shortest path from i to j, except j itself.
    """
    k = kIntermediate[i][j]
    if k == 0:  # Direct path from i to j
        print(i, end=" ")  # Print i only, omit j for now
    else:
        list_path(i, k)  # Print path from i to k
        list_path(k, j)  # Print path from k to j

The algo is O(n^3) and path recovery is proportional to the length of the path