[벨만-포드 알고리즘] 한 살도 이해하는 벨만-포드 알고리즘(Bellman-Ford Algorithm)

벨만-포드 알고리즘이란?

한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다.

음의 가중치를 갖는 edge(간선)이 있을 때 사용하는 알고리즘이다.

 

다익스트라 알고리즘과 차이는 무엇인가?

다익스트라 알고리즘

- 매번 방문하지 않는 노드 중에서 최단거리가 가장 짧은 노드를 선택해 최단 거리를 구해나간다.

- 음의 가중치를 갖는 edge(간선)이 없다면 최적의 해를 찾을 수 있다.

- 시간 복잡도가 빠르다.

 

벨만-포드 알고리즘

- 매 단계마다 모든 edge(간선)을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다.

- 음의 가중치를 갖는 edge가 있어도 최적의 해를 찾을 수 있다.

- 시간 복잡도가 느리다.

 

즉, 모든 edge의 가중치가 양수일 때는 다익스트라 알고리즘을,

음의 가중치를 갖는 edge가 존재하면 벨만-포드 알고리즘을 사용하면 된다.

 

직적 벨만-포드 알고리즘을 사용해보자!

그래프와 각 노드까지의 최단 거리를 기록하는 표(distance라고 명명)

---

STEP 0.

다음과 같은 그래프가 주어졌다고 하자.

그리고, 출발지 노드(여기선 '집'을 출발지로 가정했다)로부터 각 노드까지 최단거리를 기록하는 표를 만든다.

이 표를 앞으로 설명의 편의를 위해 distance라고 하겠다.

우선은 모든 노드의 거리를 무한대로 설정해 놓자. 그리고 출발지의 거리는 0으로 바꾼다(출발지에서 출발지는 거리가 0이므로)

이제부터 (총 노드의 개수 - 1)만큼 Cycle을 돌면서 벨만-포드 알고리즘으로 최단 거리를 찾아보자!

---

Cycle 1.

edge를 최대 1개까지 써서 갈 수 있는 노드까지 방문해서, 거리를 비교해 최단 거리를 정한다. (빨간색 간선이 edge 1개를 써서 이동한 것을 나타낸다)

현재 출발지인 집에서 edge 1개를 써서 이동할 수 있는 곳은 학교와 마트이다.

각각 학교는 -1 만큼, 마트는 4만큼 가중치(거리)가 들고, 무한대보다 작으니 최단 거리로 각각 바꿔준다.

 

edge 최대 1개만 사용해서 이동, 거리를 비교

---

Cycle 2.

edge를 최대 2개까지 써서 갈 수 있는 노드까지 방문해서, 거리를 비교해 최단 거리를 정한다.

edge 최대 2개만 사용해서 이동, 거리를 비교

---

Cycle 3.

edge를 최대 3개까지 써서 갈 수 있는 노드까지 방문해서, 거리를 비교해 최단 거리를 정한다.

edge 최대 3개만 사용해서 이동, 거리를 비교

Cycle 4.

edge를 최대 4개까지 써서 갈 수 있는 노드까지 방문해서, 거리를 비교해 최단 거리를 정한다.

edge 최대 4개만 사용해서 이동, 거리를 비교

 

 

---

벨만-포드 Python 코드

 

def bellman_ford(graph, start):
    distance = dict()
    for node in graph:
        #distance[node]는 해당 node까지 거리의 최솟값
        distance[node] = float('inf')
    distance[start] = 0
    V = len(graph) # 노드 개수
    print("distance:",distance)
    print("------start------")
    
    for _ in range(V-1):
        # edge  비교 (edge에는 <출발 노드, 도착 노드, 거리(가중치)>가 있으므로 dictionary에서 edge 정보를 for문으로 꺼내왔다)
         for node in graph:
            print("-------node--:", node)
            for neighbor in graph[node]:
                # 지금까지의 neighbor까지의 거리보다, 현재 정점(node)를 거쳐 neighbor까지 가는 거리가 더 작을 경우
                if distance[neighbor] > distance[node] + graph[node][neighbor]:
                    distance[neighbor] = distance[node] + graph[node][neighbor]                                    
                    print("distance:",distance)

    	 print(f'{_+1}사이클 끝\n')
    
    
    # 음수 사이클 판별
    for node in graph:
        for neighbor in graph[node]:
            if distance[neighbor] > distance[node] + graph[node][neighbor]:
                return -1
            
    return distance

 

진행 과정 및 출력 결과

 

distance: {'집': 0, '학교': inf, '마트': inf, '박물관': inf, '영화관': inf}
predecessor: {'집': None, '학교': None, '마트': None, '박물관': None, '영화관': None}
------start------
-------node--: 집
distance: {'집': 0, '학교': -1, '마트': inf, '박물관': inf, '영화관': inf}
distance: {'집': 0, '학교': -1, '마트': 4, '박물관': inf, '영화관': inf}
-------node--: 학교
distance: {'집': 0, '학교': -1, '마트': 4, '박물관': 1, '영화관': inf}
distance: {'집': 0, '학교': -1, '마트': 4, '박물관': 1, '영화관': 0}
distance: {'집': 0, '학교': -1, '마트': 2, '박물관': 1, '영화관': 0}
-------node--: 마트
-------node--: 박물관
distance: {'집': 0, '학교': -1, '마트': 2, '박물관': 1, '영화관': -2}
-------node--: 영화관
1사이클 끝

-------node--: 집
-------node--: 학교
-------node--: 마트
-------node--: 박물관
-------node--: 영화관
2사이클 끝

-------node--: 집
-------node--: 학교
-------node--: 마트
-------node--: 박물관
-------node--: 영화관
3사이클 끝

-------node--: 집
-------node--: 학교
-------node--: 마트
-------node--: 박물관
-------node--: 영화관
4사이클 끝

 

---

시간 복잡도

(노드의 개수 - 1) Cycle을 돌고, 각 Cycle마다 모든 Edge를 확인하므로

노드의 개수를 V라고 하고, Edge의 갯수를 E라고 하면,

시간복잡도는 O( |V-1|*|E| ) = O ( |V||E|) 

 

공간 복잡도

각 노드마다 매 순간 최단 거리를 저장해야 하므로 공간 복잡도는 O(|V|)