다익스트라 알고리즘 대충 정리

어떤 문제를 해결하기 위해?

• 그래프의 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제(single source shortest path problem)

cf) 그래프의 정점끼리 최단 경로 구하는 다른 문제는 다음과 같다.

• 하나의 정점에서 다른 하나의 정점까지의 최단 경로 구하는 문제(single source and single destination shortest path problem)
• 하나의 목적지로 가는 모든 최단 경로를 구하는 문제(single destination shortest path problem)
• 모든 최단 경로 구하는 문제(all pairs shortest path problem)

기본 전제

• 단 하나의 간선(정점과 정점을 잇는 선)이라도 가중치가 음수이면 안 된다.

음수이면 안 되는 이유?

• <가중치 합이 음수인 사이클 가능성>

  • 아래와 같은 케이스의 경우 1 -> 2 -> 3의 순환을 계속하면 가중치의 합이 무한히 작아질 수 있다.
    

• <실제 최단 거리를 못 찾을 가능성>

  • 아래와 같은 케이스의 경우 1->2->3의 경우가 1->3보다 가중치의 합이 적지만 다익스트라 알고리즘에서는 1번에서 탐색할 때 3번까지의 거리가 가장 짧아서 3번을 먼저 방문하고, 그 다음 2번을 방문할 때에는 3번은 이미 방문하였기에 1->2->3의 경로는 탐색하지 않게 된다.
    

    

기본 아이디어

• 출발점으로부터 연결되어 있는 정점들을 추가해가면서 최단 거리를 갱신(초기에는 모두 INF 값을 가짐)

로직

1. 시작 정점에서 각 정점까지의 거리를 모두 INF로 초기화하여 어딘가(배열 or 우선순위 큐; D[]라고 하자)에 담는다.
2. A라는 변수에 시작 정점(위치)을 담는다. 시작 정점을 방문했다고 체크해준다.
3. 시작 정점에서 A정점까지의 거리와 A정점에서 A정점의 인접 정점(B)까지의 거리를 더한다(dist{start, A} + dist{A, B})(방문했다고 체크되지 않은 정점만 계산한다)
4. 시작 정점에서 B정점까지의 거리를 구한다(한번도 갱신하지 않았다면 INF로 되어있을 것이다).
5. 만약 3.에서 구한 값이 4.보다 작다면 작은 값으로 D[]에 갱신해준다.
6. A의 모든 인접 정점에 대해 3~5를 시행한다.
7. '모든 방문되지 않은 정점' 중에서 시작점에서 해당 인접 정점까지의 거리가 가장 작은 정점을 선택하여 A에 할당한다.
8. 3.으로 간다.

가장 작은 거리가 기록된 곳으로만 방문했을 때 놓치는 최단 거리가 있지 않을지?

a, b, c, d의 정점 네 개가 있다고 가정해보자.
a에서 b, c로 갈 수 있고, b, c에서 d의 방향으로 연결되어 있다.
a와 b의 거리가 2, a와 c의 거리가 5이고 a가 시작점이다.
처음에 a에서 거리를 계산할 때 최단 거리 테이블에서 b까지의 거리는 INF에서 2로, c까지의 거리는 INF에서 5로 갱신된다.
이 때 최단 경로 테이블에서 b가 제일 작으므로 b로 이동하고 b는 방문했다고 체크한다.
그런데 b에서 d로만 간선이 있고 거리가 2라 하면, 최단 경로 테이블에서 d는 2+2=4로 기록된다.
최단 경로 테이블에서 방문되지 않은 정점 중 가장 작은 정점은 d이므로 d를 방문하고 방문했다고 체크하게 된다.
a에서 b와 c중 b를 방문하고 뒤이어 d를 방문하면 c를 통해서 d를 방문하지 못하게 된다.
그렇게 되면 d까지의 최단경로 중 a->c->d의 가능성을 배제시켜버리는 것이 아닌가 하는 우려를 가질 수 있다.
하지만 다음을 보면 어떤 정점을 방문하는 것은 다른 최단 경로의 가능성이 없는 경우밖에 없음을 알 수 있다.
a->c->d가 a->b->d보다 짧은 경로인데 a->b->d의 순서로 방문했다고 가정해보자
그러면 dist[a->c] <= dist[a->c->d] < dist[a->b->d]이므로 b를 방문했을 때 d의 최단 경로 테이블을 갱신했더라도 최단 경로 테이블에서 방문하지 않은 c, d 중에서 c의 값이 더 작으므로 c를 먼저 방문하고 d를 방문하지 않게 된다.
따라서 a->c->d가 a->b->d보다 짧은 경로인데 a->b->d로 d를 먼저 방문해버리는 일은 없게 된다.