BFS 알고리즘으로 다익스트라 알고리즘 유도하기

Single source shortest path

• unweighted graph → BFS
• weighted graph with nonnegative weights → Dijkstra
• weighted graph with negative weights → Bellman-ford, SPFA
• directed acyclic graph → topological sorting

용어 정의

• 경로의 길이 : 경로가 지나는 간선의 가중치의 합
• 정점 \(u\)에서 정점 \(v\)의 최단경로 : u에서 v로 가는 경로의 길이가 최소인 경로
• 간선의 완화(edge relaxation) : 정점 \(u\)에서 \(v\)로의 간선에 대해 dist[\(v\)] > dist[\(u\)] + weight(\(u, v\)) 만족하면 dist[\(v\)]를 dist[\(u\)] + weight(\(u, v\))로 업데이트시켜 주는 과정

BFS를 다익스트라로 바꾸기

BFS를 다익스트라로 바꿔보자!

1. 기본적인 bfs

1. 큐에 시작점 start를 넣는다.
2. 큐에서 정점 한 개(here)을 뽑는다.
3. here과 인접한 모든 정점(there)에 대해
    3-1. 큐에 there이 들어간적이 없다면
    3-2. dist[there] = dist[here] + 1
    3-3. 큐에 there을 넣는다.
4. 큐에 원소가 있다면 2번 과정을 반복한다.

2. 가중치 바꾸기

가중치가 없는(가중치가 모두 동일한) 그래프에서 사용한 bfs를 가중치가 있는 그래프에서 사용해야 하니 가중치를 바꿔주자.

1. 큐에 시작점 start를 넣는다.
2. 큐에서 정점 한 개(here)을 뽑는다.
3. here과 인접한 모든 정점(there)에 대해
    3-1. 큐에 there이 들어간적이 없다면
    3-2. dist[there] = dist[here] + weight[here][there]
    3-3. 큐에 there을 넣는다.
4. 큐에 원소가 있다면 2번 과정을 반복한다.

3. 우선순위 큐로 바꾸기

BFS를 이용해 정점 \(u\)에서 \(v\)까지 최단 경로를 구했다면 정점 \(u\)에서 최단 경로에 속한 정점들까지 거리도 최단경로이다. 
BFS는 인접한 정점들을 차례대로 방문하기때문에 큐에 저장된 원소들은 시작 정점으로부터 거리가 짧은 순으로 저장되지만 가중치를 바꿨기 때문에 더 이상 큐에 거리가 짧은 순으로 원소가 저장되지 않는다. 큐를 min-heap으로 바꿔 정렬된 상태로 관리해 보자.

1. 우선순위 큐에 시작점 start를 넣는다.
2. 우선순위 큐에서 정점 한 개(here)을 뽑는다.
3. here과 인접한 모든 정점(there)에 대해
    3-1. 우선순위 큐에 there이 들어간적이 없다면
    3-2. dist[there] = dist[here] + weight[here][there]
    3-3. 우선순위 큐에 there을 넣는다.
4. 우선순위 큐에 원소가 있다면 2번 과정을 반복한다.

4. 거리 순으로 정렬하기

우선순위 큐는 거리가 짧은 순으로 원소를 가지고 있어야 한다. 따라서 큐에 거리 정보도 같이 넣어주자.

1. 우선순위 큐에 (0, start)를 넣는다.
2. 우선순위 큐에서 (here_dist, here)을 뽑는다.
3. here과 인접한 모든 정점(there)에 대해
    3-1. 우선순위 큐에 there이 들어간적이 없다면
    3-2. dist[there] = here_dist + weight[here][there]
    3-3. 우선순위 큐에 (dist[there], there)을 넣는다.
4. 우선순위 큐에 원소가 있다면 2번 과정을 반복한다.

5. 정점 여러 개 넣기

지금까지 코드는 큐에 넣은 정점은 다시 큐에 넣지 않는다. 하지만 가중치가 있는 그래프에서는 나중에 발견한 경로가 더 짧은 경우가 존재할 수 있다. 
\(u\) → \(b\)까지 거리가 7인 경로를 발견하여 사실 \(u\) → \(a\) → \(b\)의 경로는 발견하지 못한다. 정점이 큐에 여러 번 들어갈 수 있게 수정해 보자.

1. 우선순위 큐에 (0, start)를 넣는다.
2. 우선순위 큐에서 (here_dist, here)을 뽑는다.
3. here과 인접한 모든 정점(there)에 대해
    3-1. dist[there] > here_dist + weight[here][there]라면
    3-2. dist[there] = here_dist + weight[here][there]
    3-3. 우선순위 큐에 (dist[there], there)을 넣는다.
4. 우선순위 큐에 원소가 있다면 2번 과정을 반복한다.

6. 초기값 정하기

dist[there] > here_dist + weight[here][there]로 인해 시작점을 제외한 모든 정점까지의 거리를 엄청 큰 값으로 초기화하자.

초기화: 시작점을 제외한 모든 정점에 대해 dist의 값은 무한히 큰 값
1. 우선순위 큐에 (0, start)를 넣는다.
2. 우선순위 큐에서 (here_dist, here)을 뽑는다.
3. here과 인접한 모든 정점(there)에 대해
    3-1. dist[there] > here_dist + weight[here][there]라면
    3-2. dist[there] = here_dist + weight[here][there]
    3-3. 우선순위 큐에 (dist[there], there)을 넣는다.
4. 우선순위 큐에 원소가 있다면 2번 과정을 반복한다.

7. 모든 정점에 대해 3번 과정 1번만 실행하기

5번에서 정점을 큐에 여러 번 넣는 것을 허용했다. 어떤 정점 \(i\)에 대해 i까지의 최단 경로가 계속 발견되어 dist[\(i\)]가 여러 번 초기화되었다고 가정해 보자.

우선순위 큐에는 정점 \(i\)와 같이 넣은 dist[\(i\)]의 값이 (\(i_{dist}\), \(i\)) 형태로 다양하게 존재할 것이다. 그로 인해 우선순위 큐에서 뽑힌 (\(i_{dist}\), \(i\))의 \(i_{dist}\)는 사실 마지막에 갱신된 최단 경로를 나타내는 dist[\(i\)]와 값이 다름에도 의미 없는 3번 과정을 진행할 것이다. \(i_{dist}\)가 최소 값이 아니면 3번 과정을 생략하자.

초기화: 시작점을 제외한 모든 정점에 대해 dist의 값은 무한히 큰 값
1. 우선순위 큐에 (0, start)를 넣는다.
2. 우선순위 큐에서 (here_dist, here)을 뽑는다.
3. here_dist > dist[here] 이라면 4번 과정을 생략한다.
4. here과 인접한 모든 정점(there)에 대해
    4-1. dist[there] > here_dist + weight[here][there]라면
    4-2. dist[there] = here_dist + weight[here][there]
    4-3. 우선순위 큐에 (dist[there], there)을 넣는다.
5. 우선순위 큐에 원소가 있다면 2번 과정을 반복한다.

시간 복잡도 분석

모든 정점은 우선순위 큐에 중복해서 들어갈 수 있지만 우선순위 큐에서 뽑은 정점(here)의 거리(d)가 현재 최단 경로의 길이(dist[here]) 보다 크다면 빨간색 부분을 실행하지 않았다. 빨간색 부분은 모든 정점에 대해 한 번씩만 실행되므로 \(O(E)\)번 실행된다.

우선순위 큐의 삽입과 삭제에 걸리는 시간을 알기 위해서는 우선순위 큐에 삽입되는 원소의 최대 개수를 알아야 한다. 빨간색 부분에서 간선의 완화가 매 순간 실행되어 우선순위 큐에 원소가 삽입되는 것이 최악의 상황이므로 우선순위 큐에는 최대 \(E\)개의 원소가 삽입된다. 따라서 우선순위 큐의 삽입 삭제는 \(O(logE)\)의 시간이 걸린다.

종합하면 \(E\)번 간선의 완화가 될 때 원소가 \(logE\)에 삽입되므로 시간 복잡도는 \(O(ElogE)\)이다. \(E \le V^{2}\)이므로 \(O(ElogV)\)라고도 할 수 있다.

특징

음수 가중치가 있을 때는 시간 복잡도가 보장되지 않으며 음의 사이클이 있으면 무한루프를 돌게 된다.

다익스트라 알고리즘 과정 중 우선순위 큐에서 뽑힌 정점이 의미하는 것은 현재 방문하지 않은 정점들 중 출발점에서 거리가 가장 가까운 정점으로 방문하지 않은 다른 정점들에 의해 뽑힌 정점의 거리가 갱신되는 일이 발생하지 않는다는 것을 의미한다. 하지만 음수 가중치가 있는 경우에는 음수 가중치를 가진 아직 방문하지 않은 정점에 의해 현재 정점까지의 거리가 더 짧아지는 경우의 수가 발생하기 때문에 시간 복잡도가 보장되지 않는다. 따라서 다익스트라 알고리즘은 양수 가중치가 있는 그래프에서 사용해야 한다.