Bellman-Ford Shortest Path Algorithm

• Bellman-Ford (adjacency list, negative cycles) - O(VE)
• Bellman-Ford (edge list, negative cycles, fast & optimized) - O(VE)

 

Bellman Ford Algorithm Key Features

 

1. Start 노드를 규정하고 다른 모든 노드들의 최단 거리를 계산하는 알고리즘이다.

( SSSP Algorithm; Single Source Shortest Path)

 

2. 음의 간선이 존재해도 동작한다.

 

 

Brief Steps for finding shortest Path 

 

1. src (start) 이외의 모든 노드의 비용을 양의 무한대로 초기화 한다.

 

2. v-1 회만큼 모든 Edge를 순회하며 아래 조건을 반복한다. (이 단계를 'relaxation' 이라 함)

- if dist[edge.from] + edge.cost <  dist[edge.cost]

             dist[edge.to] = dist[edge.from] + edge.cost

 

3. (2) 조건을 한번 더 반복하여 relaxation이 가능한 노드를 확인한다.

 

 

 

* relaxation 과정의 outer-loop는 왜 v-1 번 수행하는가 ? 

 

->  모든 Edge에 대해 한번의 순회의 계산은, Path에서 최소 1번의 Edge를 거치는 Shortest Path의 안정화를 보장한다. 

즉, i번의 순회는 최소 i개의 edge를 거치는 Shorterst Path를 안정화 보장시킨다는 의미이고,

Path는 최대 V-1개의 Edge를 갖을 수 있으므로 outer loop는 v-1 회 반복해야한다.

 

 

• Bellman-Ford (adjacency list, negative cycles) - O(VE)

# pseudo code 

def bellmanFord(src: int, edges: List[Edge]) -> list:
    distances = [POSITIVE_INF] * n
    distances[src] = 0
    
    # relaxation
    for _ in range(v-1): # v is the number of vertexies
        for edge in edges:
            if distances[edge.from] + edge.cost < distances[edge.to]:
                distances[edge.to] = distances[edge.from] + edge.cost
     
    # detect negative-cycle.
    for _ in range(v-1): # v is the number of vertexies
        for edge in edges:
            # The node is in negative-cycle if it is possible to relaxation
            if distances[edge.from] + edge.cost < distances[edge.to]:
                distances[edge.to] = NEGATIVE_INF

    return distances

 

Bellman-Ford (edge list, negative cycles, fast & optimized) - O(VE)

 

최적화 아이디어는 굉장히 간단하다. 

 

앞서 설명했듯, 순회문이 V-1인 이유는 Worst Case를 염두에 두기 때문이다.

 

이를 감지하는 Boolean을 두면 최적화 여지가 있다.

 

# pseudo code 

def bellmanFord(src: int, edges: List[Edge]) -> list:
    distances = [POSITIVE_INF] * n
    distances[src] = 0
    bool relaxed # here !
    
    # relaxation
    for _ in range(v-1):
    	relaxed = False # here !
    	for edge in edges:
            if distances[edge.from] + edge.cost < distances[edge.to]:
                distances[edge.to] = distances[edge.from] + edge.cost
                relaxed = True # here ! 
     	
        if relaxed == False: # relaxation 이 없었으면, 순회문을 반복할 이유가 없다.
            break

    # detect negative-cycle.
    for _ in range(v-1):
    	relaxed = False
        for edge in edges:
            if distances[edge.from] + edge.cost < distances[edge.to]:
                distances[edge.to] = NEGATIVE_INF
                relaxed = True # here !
                
        if relaxed == False: # here !
            break

    return distances