그래프 최단경로 알고리즘 - 플로이드워셜, 다익스트라, 벨만포드, SPFA 정리

그래프에서 최단경로를 구하는 대표적인 알고리즘 4개를 소개할 것이다.

정점의 개수는 V(vertex), 간선의 개수는 E(edge)로 표기한다.

 

1. Floyd - Warshall 알고리즘

모든 정점 간의 최단거리를 구하는 알고리즘이다.

개념과 구현 모두 아주 간단한데, 그냥 중간 정점 k를 거치면서 i에서 j로 가는 최단경로를 갱신해나가면 된다.

k를 1부터 N까지 돌면서 중간 정점으로 1~k를 사용하며 i->j로 가는 최단 경로를 저장한다.

adjMat[i][k]와 adjMat[k][j]에 저장된 값은 중간 정점으로 1~k-1을 사용하는 최단 경로일 것이다.

여기서 중간 정점 k를 사용할 때 거리가 더 짧아진다면 adjMat[i][j]가 갱신될 것이다.

 

매우 간단한 알고리즘이지만, 시간복잡도가 O(V^3)이고, 모든 정점 간의 거리를 구하는 문제가 많지 않기 때문에 잘 쓰이지 않는다.

 

2. Dijkstra 알고리즘

하나의 시작점으로부터 각 정점에 이르는 최단 거리를 구하는 알고리즘이다.

간선에 음의 가중치를 사용할 수 없다는 특징이 있다.

 

dist 배열에 시작점으로부터 각 정점까지의 최단 경로를 저장하는데, 탐색을 시작하기 전에 dist 배열을 무한대로 초기화시켜준다.

그리고 dist[시작점] 을 0으로 초기화시켜준다.

우선 순위 큐를 이용하는 알고리즘인데, 큐 안에는 정점과 해당 정점까지의 거리를 구조체로 저장한다.

큐가 비어있을 때까지 top을 가져와서 해당 정점과 연결된 정점들을 순회하며 연결된 정점으로 갔을 때 거리가 작아지면 업데이트를 하고 큐에 push를 해준다.

이 작업을 반복하면 끝이다.

코드와 비교하면서 보면 이해하기 쉬운 알고리즘이다.

시간복잡도는 O(ElogV) 이며, 자주 사용되는 최단 경로 알고리즘이다.

 

3. Bellman-Ford 알고리즘

다익스트라와 마찬가지로 하나의 시작점으로부터 각 정점에 이르는 최단 거리를 구하는 알고리즘이다.

간선에 음의 가중치를 허용하고, 음의 싸이클은 허용하지 않는다.

 

탐색 과정은 다익스트라보다 간단한데, 다익스트라에서는 정점에 기준을 맞춰 최단 경로를 저장해 나갔다면

벨만포드에서는 간선에 기준을 맞춘다.

모든 간선에 대해서 시작점(s), 도착점(e), 가중치(w) 에 대해서 dist[e]가 dist[s]+w보다 크다면 업데이트를 해준다.

그냥 이 과정을 V번 반복하면 된다.

그런데 만약 V번째에도 업데이트가 일어난다면 음의 싸이클이 존재한다는 뜻이다.

시간복잡도는 O(E*V)이다.

음의 가중치가 없는 상황에서는 그냥 다익스트라를 쓰면 O(ElogV) 만에 해결할 수 있어서 굳이 안 쓰지만

음의 가중치가 있는 상황에서 필요한 최단 경로 알고리즘이다.

 

4. SPFA(Shortest Path Faster Algorithm)

벨만-포드 알고리즘을 개선한 알고리즘이다.

모든 간선을 탐색하는 것이 아니라, 큐에 담긴 정점과 연결된 간선만을 탐색한다.

처음에 시작점을 큐에 담고, 이후에는 업데이트가 일어났을 때 연결된 정점이 큐에 없다면 push를 해준다.

큐에 있는지 없는지는 isinQ 배열을 이용해서 판단한다.

이렇게 하면 랜덤데이터에 경우에는 O(E)의 시간복잡도를 가지지만, 최악의 경우에는 O(E*V)의 시간복잡도를 가진다.