[알고리즘] 다익스트라, 벨만포드 알고리즘(Dijkstra & Bellman-ford)

📕다익스트라 알고리즘

---

다익스트라 알고리즘은 가장 빠른 길을 찾을 때 주로 사용하는 알고리즘이다.

 

빠른 길을 찾을때 사용한다고? 그럼 BFS쓰면 되는거 아닌가? 라고 생각할 수 있다.

맞다 BFS를 사용하면 되지만 BFS를 사용하지 못하는 경우가 존재하는데

바로 비용이 존재할때이다.

BFS의 경우 모든 간선의 비용이 동일해야하지만, 다익스트라는 모든 간선의 비용의 동일하지 않아도 사용가능하다.

 

다익스트라 알고리즘은 min_heap 우선순위큐를 사용하고, 간선을 키값으로 사용한다.

 

다익스트라 알고리즘에서 핵심은 e = w->  x 이다.

즉,dist[x] <= dist[w] + e.weight() 인 것이다.

 

 

그래프 X의 Source 노드 s에서 출발한다.

0과 연결되어 있는 노드 1 7 4 의 비용을 업데이트 하고 0을 집합 X에 추가하고처리 한 후,

업데이트한 간선 중 가장 비용이 저렴한 노드를 다음 source노드로 설정한다.

위와 같은 과정을 모든 노드가 집합 X에 포함될때까지 반복한다.

 

의사코드를 보자.

Dijkstra(G, w, s):

Initialize-sigle-soure(G, s)
S = 0
Q = G.V
while Q != 0
	u = Extract_min(Q)
    S = S U {u{
    for each vertex v ∊ G.Adj[u]
    	relax(u, v,w)

이때 큐는 V-X 즉, V 차집합 X이다.

 

다익스트라 알고리즘의 시간복잡도는 정렬되지 않은 배열을 사용할 경우, V^2이고

바이너리 힙을 사용할 경우 O(ElogV)이다.

 

지금까지 다익스트라 알고리즘으로 최단경로를 찾는 것을 알아보았다.

하지만 다익스트라 알고리즘도 cover할 수 없는 부분이 있는데,

바로 간선의 비용이 음수인 경우이다.

 

간선의 비용이 음수이면 만약 0에서 1을 가는 비용이 4, 0에서 3을 가는 비용이 2,

1에서 2를 가는 비용이 6, 2에서 3을 가는 비용이 -9라고 해보자.

 

그렇다면 0에서 3으로 가는 최단경로는 당연히 0->1->2->3이 될 것이다.

하지만 다익스트라 알고리즘은 음수를 처리하지 못하기 때문에 각각의 간선에 음수비용의 양수값인 9를 더해준다.

그렇면 모두 9씩 증가한 13, 11, 15, 0이 되는데

이때, 0에서 3으로 가는 최단경로가 0->1->-2>-3이 아닌

0->3으로 바뀌게 된다.

 

그렇기 떄문에 우리는 이러한 문제를 해결하기 위해 다른 알고리즘을 써야하고

그것이 바로 벨만포드 알고리즘이다.

 

벨만포드 알고리즘은 다음 글에서 소개하도록 하겠다.