[자료구조 및 알고리즘] 최단경로 알고리즘

최단경로 알고리즘

BFS
시작점으로부터 거리가 가까운 정점부터 탐색
가중치가 없는 그래프의 최단 경로를 찾는 데 쓰일 수 있다.

간선의 가중치가 있는 그래프의 최단 경로는 어떻게 찾을까
 - Dijkstra 알고리즘
 - Bellman-Ford 알고리즘
 - SPFA 알고리즘
 - Floyd 알고리즘

경로의 길이: 경로가 지나는 간선의 가중치의 합
v1에서 v2로 가는 되단 경로: v1에서 v2로 가는, 경로의 길이가 최소인 경로

너비 우선 탐색(BFS)
1. 시작점을 큐에 넣는다
2. 큐에서 정점 하나를 뺀다.
3. 이 정점에 연결된 모든 정점들을 큐에 넣는다. (단, 큐에 이미 들어갔던 정점은 제외) dist[i] = dist[x] + 1
4. 큐에 원소가 남아 있다면 2번으로 돌아간다.

Dijkstra 알고리즘
0. 간선 가중치가 양수인 경우에 사용가능
1. 시작점 start를 우선순위 큐에 넣는다.
2. 우선순위 큐에서 정점 x를 뺀다.
3. dist[x] != 우선순위 큐에서 빼낸 dist값이라면 4번을 그냥 넘어간다. (1번만 실행되어야하기 때문이다)
4. 정점 x에 연결된 각각의 정점 i에 대해, dist[i] > dist[x]+간선의 길이라면,
 - 1. dist[i] = dist[x]+(간선의 길이)
 - 2. 정점 i를 우선순위 큐에 넣는다.
5. 우선순위 큐에 원소가 남아 있다면 2번으로 돌아간다.

시간복잡도

각 간선은 한 번씩만 우선순위 큐에 들어간다.
우선순위 큐에 원소가 들어가는 횟수는 많아야 O(E)번
∴  O(ElogV)

주의사항

가중치가 음수인 간선이 존재할 때에는 시간 복잡도가 보장되지 않는다.
그래프에 음의 사이클이 있으면 무한 루프를 돌게 된다.

Bellman-ford 알고리즘

 

벨만-포드 알고리즘은 음수 간선이 포함된 상황에서 사용할 수 있는 알고리즘이다. 음수 간선이 포함되어도 다익스트라를 이용해 최단 거리를 계산할 수는 있다. 단, 음수 간선의 순환이 포함된다면 최단 거리가 음의 무한인 노드가 발생한다. 무한으로 줄일 수 있기 때문이다.

따라서 이런 경우에는 벨만-포드 알고리즘을 이용해 최단 거리를 구해야 한다. 해당 알고리즘은 음의 간선이 포함된 상태에서도 사용할 수 있다. 또한 음수 간선의 순환을 감지할 수 있다. 그리고 벨만-포드 알고리즘은 기본적으로 다익스트라 알고리즘의 최적해를 포함하고 있다. 벨만 포드의 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느리다.

 

1. dist[start] = 0 나머지 i에 대해 dist[i] = INF
2. 각 간선 (u,v) (길이 = l)에 대해, dist[v] = min(dist[v], dist[u]+l) (간선완화)
3. 2번 과정을 v-1번 반복해준다.

증명
임의의 점 v에 대해서 시작점 start에서 v까지의 최단경로가 존재한다.

간선 완화를 경로의 길이만큼 반복해주면 start에서 v까지의 최단 경로가 구해진다.
최단 경로는 단순경로이므로 최단 경로의 길이는 많아야 v-1
∴ 완화 과정을 v-1번 반복하면 모든 최단경로를 구할 수 있다.
O(VE)

위 증명은 간선의 가중치가 양수라는 사실이 이용되지 않았다.

다만 완화 과정이 v-1번에 안끝나는 경우가 한 가지 존재한다.
그래프에서 음의 사이클이 있을 때.
이를 이용해 그래프에 음의 사이클이 존재하는지 체크할 수 있다.

SPFA 알고리즘

Bellman-Ford 알고리즘을 큐를 이용한 최적화

dist[start] = 0, 나머지 i에 대해 dist[i] = INF로 초기화

1. 시작점 start를 큐에 넣는다
2. 큐에서 원소 x를 뺀다
3. 정점 x에 연결된 각각의 정점 i에 대해
 - 1. dist[i] = min(dist[i], dist[x] + 간선의 길이)
  - 2. 간선이 성공적으로 완화되었을 경우, 지금 정점 i가 큐에 들어있지 않다면, 큐에 넣는다
4. 큐에 원소가 남아있다면 2번으로 돌아간다.

SPFA 알고리즘 역시 최악의 경우 O(VE)의 시간 복잡도를 갖는다.
그러나, 평균적으로 O(E)에 작동함이 실험적으로 알려져 있다.

플로이드 알고리즘

정점이 주어졌을 때, 다른 모든 점들에 대한 최단경로를 구했던 위 알고리즘과는 차이가 있음.

플로이드 알고리즘: 모든 가능한 시작 정점과 모든 가능한 끝 정점에 대해 u에서 v로 가는 최단 경로의 길이를 모두 구하여라.

 

임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이 노드인 m에대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다.

 

dp[k][x][y] : 정점 x에서 y로 가는, 중간에 1번부터 k번 사이의 정점만 지나는 최단거리
초기조건: dp[0][x][y]는 x와 y 사이 간선이 있을 때에만 간선의 길이, 아니면 INF로 초기화. 혹시 같은 간선에 길이가 들어오면 더 짧은 값을 할당해주면 된다.

점화식: dp[x][y] = min(dp[x][y], dp[x][k]+dp[k][y])

3중 for문 1번만 돌면 최단거리를 구할 수 있다.
먼저, dist[i][j] = INF, dist[i][i] = 0으로 초기화 해준다.
간선을 입력 받을 때마다 dist[i][j] = min(dist[i][j],length)로 처리해준다.

시간복잡도: O(V^3)

길이가 음수인 간선이 존재해도 잘 작동한다.

모든 간선의 길이가 양수라면 다익스트라 알고리즘을 V번 돌리면 O(VElogV).

플로이드 알고리즘은 구현량이 매우 적고 실제 작동 속도는 상당히 빠르다.