[Python] Bellman-Ford's Shortest Path

The Bellman-Ford shortest path algorithm, created by Richard Bellman and Lester Ford, Jr,. determines the shortest path from a start vertex to each vertex in a graph. 

For each vertex, the Bellman-Ford algorithm determines the vertex's distance and predecessor pointer. A vertex's distance is the shortest path distance from the start vertex. A vertex's predecessor pointer points to the previous vertex along the shortest path from the start vertex. 

 

The Bellman-Ford algorithm initializes all vertices' current distances to infinity (∞) and predecessors to null, and assigns the start vertex with a distance of 0. The algorithm performs V-1 main iterations, visiting all vertices in the graph during each iteration. Each time a vertex is visited, the algorithm follows all edges to adjacent vertices. For each adjacent vertex, the algorithm computes the distance of the path from the start vertex to the current vertex and continuing on to the adjacent vertex. If that path's distance is shorter than the adjacent vertex's current distance, a shorter path has been found. The adjacent vertex's current distance is updated to the newly found shorter path's distance, and the vertex's predecessor pointer is pointed to the current vertex.

The Bellman-Ford algorithm does not require a specific order for visiting vertices during each main iteration. So after each iteration, a vertex's current distance and predecessor may not yet be the shortest path from the start vertex. The shortest path may propagate to only one vertex each iteration, requiring V-1 iterations to propagate from the start vertex to all other vertices

// Pseudocode
BellmanFord(startV) {
   for each vertex currentV in graph {
      currentV⇢distance = Infinity
      currentV⇢predV = null
   }

   // startV has a distance of 0 from itself
   startV⇢distance = 0                

   for i = 1 to number of vertices - 1 { // Main iterations
      for each vertex currentV in graph {
         for each vertex adjV adjacent to currentV {
            edgeWeight = weight of edge from currentV to adjV
            alternativePathDistance = currentV⇢distance + edgeWeight
                  
            // If shorter path from startV to adjV is found,
            // update adjV's distance and predecessor
            if (alternativePathDistance < adjV⇢distance) {
               adjV⇢distance = alternativePathDistance
               adjV⇢predV = currentV
            }
         }
      }
   }

   // Check for a negative edge weight cycle
   for each vertex currentV in graph {
      for each vertex adjV adjacent to currentV {
         edgeWeight = weight of edge from currentV to adjV
         alternativePathDistance = currentV⇢distance + edgeWeight

         // If shorter path from startV to adjV is still found,
         // a negative edge weight cycle exists
         if (alternativePathDistance < adjV⇢distance) {
            return false
         }
      }
   }

   return true
}

The Bellman-Ford algorithm supports graphs with negative edge weights. However, if a negative edge weight exists, there is no shortest path. 

 

 

한글로 정리하자면 

1. 모든 Vertex (Node) 들의 distance를 ∞, predecessor node를 null로 초기화한다.

2. 시작 vertex (startV)의 distance를 0으로 설정한다. 

3. V 개의 Vertex를 가진 Graph는 (V - 1) 번의 Main iteration (foor loop)이 존재한다. 

4. 각 Main iteration에서 모든 vertex를 방문하고 (현재 방문한 vertex를 currentV 라고 할때) 다음과 같은 절차를 따른다:

• distance 계산
  distance = (현재 방문한 currentV의 distance) + (계산하고자 하는 adjacnet vertex 까지의 path weight) 
  Ex. A (distance 10) →(weight 3)→ B 이면, B의 distance는 10 + 3 = 13
• 계산된 distance가 adjacent vertex의 distance 값보다 높다면 이를 업데이트한다.

5. 위 알고리즘을 V - 1회 반복 시 각 node의 distance가 starting vertex 부터의 거리, predecessor pointer가 최단거리 path를 나타낸다. 

 

## Python Implementation

def bellman_ford(graph, start_vertex):
    # Initialize all vertex distances to infinity and
    # and predecessor vertices to None.
    for current_vertex in graph.adjacency_list:
      current_vertex.distance = float('inf') # Infinity
      current_vertex.pred_vertex = None

    # start_vertex has a distance of 0 from itself
    start_vertex.distance = 0                

    # Main loop is executed |V|-1 times to guarantee minimum distances.
    for i in range(len(graph.adjacency_list)-1):
        # The main loop.
        for current_vertex in graph.adjacency_list:
            for adj_vertex in graph.adjacency_list[current_vertex]:
                edge_weight = graph.edge_weights[(current_vertex, adj_vertex)]
                alternative_path_distance = current_vertex.distance + edge_weight
                      
                # If shorter path from start_vertex to adj_vertex is found,
                # update adj_vertex's distance and predecessor
                if alternative_path_distance < adj_vertex.distance:
                   adj_vertex.distance = alternative_path_distance
                   adj_vertex.pred_vertex = current_vertex

    # Check for a negative edge weight cycle
    for current_vertex in graph.adjacency_list:
        for adj_vertex in graph.adjacency_list[current_vertex]:
             edge_weight = graph.edge_weights[(current_vertex, adj_vertex)]
             alternative_path_distance = current_vertex.distance + edge_weight

             # If shorter path from start_vertex to adj_vertex is still found,
             # a negative edge weight cycle exists
             if alternative_path_distance < adj_vertex.distance:
                return False

    return True