bellman-ford algorithm

An algorithm for finding the shortest path in a weighted graph. In short:

• iterate through all vertices V-1 times (since a path can have at most V-1 edges)
• check for negative-weight cycles

Steps:

• begin with an edge list for the graph
• create a dict to store min distances
  • to source: 0
  • to all other nodes: infinite
• for each vertex, repeat the following V-1 times:
  • for each edge (u, v) with weight w, if the distance to u plus w is less than the distance to v, update the distance to v.
• after V-1 iterations, check for negative-weight cycles by verifying if a further relaxation is possible.

def bellman_ford(graph, V, src):
    dist = [float('inf')] * V
    dist[src] = 0
    
    for _ in range(V - 1):
        for u, v, w in graph:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # Check for negative-weight cycles
    for u, v, w in graph:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return "Graph contains a negative weight cycle"
    
    return dist
 
# Example usage
graph = [
    (0, 1, -1), (0, 2, 4), (1, 2, 3),
    (1, 3, 2), (1, 4, 2), (3, 2, 5),
    (3, 1, 1), (4, 3, -3)
]
V = 5
src = 0
print(bellman_ford(graph, V, src))

SPFA §

def spfa(graph, source):
    # Initialize distances to all vertices as infinite and source's distance as 0
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    
    # Initialize queue and enqueue source vertex
    queue = deque([source])
    in_queue = {v: False for v in graph}
    in_queue[source] = True
    
    while queue:
        u = queue.popleft()
        in_queue[u] = False
        
        # Relax all adjacent vertices of u
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True
    
    return dist
 
# Example usage
if __name__ == "__main__":
    graph = defaultdict(list)
    graph[0].extend([(1, 4), (2, 5)])
    graph[1].extend([(2, -3), (3, 2)])
    graph[2].extend([(3, 4)])
    graph[3].extend([])  # No outgoing edges from vertex 3
    
    source = 0
    distances = spfa(graph, source)
    print("Shortest distances from source vertex", source)
    for vertex in distances:
        print(f"Vertex {vertex}: {distances[vertex]}")