[algorithms] ch4. Paths in graphs (Bellman-Ford's algorithm)

(23.03.19)

algorithms  S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기

http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf

 

 

정리한 내용

4.6 Shortest paths in the presence of negative edges

4.7 Shortest paths in dags

---

 

negative edges가 있는 graph에서 shortest path를 찾는 알고리즘으로는 Bellman-Ford algorithm 이 있다.

- input: graph, length_e, start_node

- output: distance_v

- 시작 노드를 제외한 나머지 노드에는 무한대, 시작노드에는 0으로 distacne 값을 설정한다.

- 모든 edge에 대해서 distance update를 수행한다. -> 이를 |V|-1 회 수행한다.

 

 

 

 

 

Bellman-Ford algorithm 수행 예시

 

 

 

 

 

Bellman-Ford algorithm은 graph에 negative cycle이 존재하면 작동하지 않는다. 

- 이를 방지하고자 Bellman-Fold algorithm에서 |V|-1 번 동안 모든 edge에 대해 distance update를 시켜준 후, 한 번 더 모든 edge에 대해서 distance update를 시켜주는데 만약 이 마지막 distance update에서 update가 일어난다면, 이는 negative cycle이 포함되어있다는 뜻이 된다. 

그림 출처: https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/

 

 

 

graph의 edge에 length가 양수라면 dijkstra 알고리즘으로 최단경로를 탐색하고, graph가 edge에 음수가 포함되어 있으면 Bellman-ford 알고리즘으로 최단경로를 탐색한다. 그렇다면, cylce이 아예 없는 directed acylic graph의 최단경로 탐색은 어떻게 할까?

- dag 에다가 DFS 적용하여 linearize 시켜서 각 edge를 update시켜주면 된다. 

 

 

 

 

 

정리해보면, graph의 shortest path를 찾는 알고리즘은 3가지로 분류해볼 수 있다.

1. positive edges -> dijkstra

2. negative edges -> Bellman-Ford 

3. cycle이 없는 graph (positive, negative 상관없음) -> dags

 

 

 

 

 

Bellman-Ford algorithm python code

# bellman-ford algorithm

def bellman_ford(graph, start_node):
    dis = {node: float('inf') for node in graph}
    dis[start_node] = 0

    for i in range(len(graph)-1):
        for node in graph:
            # node -> neighbor
            for neighbor in graph[node]:
                if dis[neighbor] > dis[node] + graph[node][neighbor]:
                    dis[neighbor] = dis[node] + graph[node][neighbor]

    # negative cycle check
    for node in graph:
        for neighbor in graph[node]:
            if dis[neighbor] > dis[node] + graph[node][neighbor]:
                return False

    return dis


if __name__ == '__main__':
    # bellman_ford - input: graph, start_node, output: distances of nodes

    # graph = dict()
    graph = {
        'A': {'B': -1, 'C': 4},
        'B': {'C': 3, 'D': 2, 'E': 2},
        'C': {},
        'D': {'B': 1, 'C': 5},
        'E': {'D': -3}
    }

    print(f"bellman_ford: {bellman_ford(graph,'A')}")

 

 

https://github.com/gompaang/algorithm_python/blob/master/bellman_ford.py

GitHub - gompaang/algorithm_python