[알고리즘] SSP(3) - 다이젝스트라 알고리즘 ( Dijkstra's Algorithm )

1. Dijkstra's 알고리즘 vs Prim's 알고리즘

SSP의 두 번째 알고리즘 Dijkstra's 알고리즘에 대해 알아보겠습니다.

Dijkstra's 알고리즘은 이전에 MST의 Prim's 알고리즘과 매우 흡사합니다.

( Prim's 알고리즘은 여기를 참고해주세요 ! )

Dijkstra's 알고리즘도 최소 우선순위 큐를 이용해서 하나의 정점으로부터 인접한 간선들을 확장해 나가는 방식입니다.

Prim's 알고리즘은 MST를 만들기 위해서 가중치와 정점의 key 값을 비교하여 key 값을 업데이트 할지 말지를 결정했습니다.

SSP에서는 이를 Relax라고 표현을 했습니다.

Relax는 key값이 없고, 최단 경로 추정 값(d[v])을 이용하여 d[v]를 업데이트 할지 말지를 결정했습니다.

그리고 Relax는 정점의 key값이 딱 주어진 것이 아니라 최단 경로 추정 값들이 누적되어온 결과입니다.

이런 점에서 Prim's 알고리즘과 Dijkstra's 알고리즘은 다릅니다.

Dijkstra's 알고리즘의 동작하는 방식은 Prim's 알고리즘과 비슷하므로 바로 동작 과정을 살펴보도록 하겠습니다.

2. Dijkstra's 알고리즘

Dijkstra's 알고리즘은 먼저 모든 정점들을 최소 우선순위 큐에 삽입합니다.

그리고 최단 경로 가중치 값( d[v] )이 가장 작은 정점을 선택하여 인접 간선들에 대해 Relax를 수행하여, 시작 정점으로부터 각 정점까지의 최단 경로 비용을 계산합니다.

초기화된 그래프의 모습입니다.

시작정점을 제외하고 모든 정점의 값은 입니다.

최소 우선순위 큐에서 값이 가장 작은 정점을 추출( extract )하므로

v1 정점을 시작으로 하여 간선을 확장해나갑니다.

인접한 간선을 선택하여 Relax를 수행합니다.

가중치가 8인 간선을 선택할 수도 있으며, 선택 순서는 구현하기에 달려있습니다.

Step 1에서 이므로

Relax 결과 으로 업데이트 됩니다.

Step 2와 같이 Relax를 수행하여 

으로 업데이트 합니다.

v1의 인접 간선들에 대해 모두 Relax를 수행했으므로,

다음 정점을 선택하기 위해 가 가장 작은 정점을 추출( extract ) 합니다.

따라서 정점 v2가 추출이 되어 인접 간선들에 대해 Relax를 수행합니다.

이고

 이므로

Relax 결과  를 업데이트 하지 않습니다.

즉 ( v1 , v4 )의 최단 경로는 v1 -> v4 입니다.

v2의 모든 인접간선에 대해 Relax를 수행했으므로

최소 우선순위 큐에서 값이 가장 작은 정점을 추출( extract )하여 정점 v5가 추출됩니다.

v5의 모든 인접간선에 대해 Relax를 수행했으므로

최소 우선순위 큐에서 값이 가장 작은 정점을 추출( extract )하여 정점 v4가 추출됩니다.

값이 같을 경우 업데이트 해도 되고 안해도 됩니다.

그런데 가만히 두는게 연산을 줄여주겠죠?

v4의 모든 인접간선에 대해 Relax를 수행했으므로

마지막 정점 v3가 추출됩니다.

Dijkstra's 알고리즘은 Prim's 알고리즘과 유사한 방식인데, key 값을 사용하는 것이 아닌 최단 경로 추정 값 을 사용하며,

업데이트를 할 때도 그대로 가중치를 업데이트 하는 것이 아니라 이전 정점까지의 최단 경로 추정 값  + 가중치 값을 업데이트 합니다.

SSP는 최단 경로와 그 비용을 구하는 것이 목적이니까요.

결과 트리를 보시면 각 정점의  값은 시작 정점으로부터 그 정점까지의 최단 경로 비용을 의미합니다.

예를들어, 의 값은 7이므로 v1 -> v5 까지의 최단 경로 비용은 7입니다.

실제로 v1 -> v2 -> v5의 경로 상 모든 가중치를 더하면 7임을 확인할 수 있습니다.

여기서 선행자를 언급을 안했는데, "최단 경로" 자체를 구하고 싶을 수가 있습니다.

그래서 Relax의 결과로  값이 업데이트가 되면 extract된 정점을 부모노드로 설정해줌으로써 각 정점의 부모 정점을 기억할 수 있습니다.

예를들어, Step 2에서 Relax 결과 업데이트가 되었으므로 정점 v2의 부모는 v1이 되는 것이죠.

3. 수도 코드

1) line 2 ~ 3

그래프를 초기화 합니다.

처음 시작할 정점을 제외한 모든 정점의 값을 로 할당하고, 처음 시작할 정점의  값은 0으로 할당합니다.

그리고 모든 정점을 최소 우선순위 큐에 삽입합니다.

2) line 4 ~ 8

최소 우선순위 큐가 비어있을 때 까지 반복문을 돕니다.

그리고 값이 가장 작은 정점을 추출하여, 그 정점과 연결된 간선에 대해 Relax를 수행합니다.

3)시간복잡도

Prim's 알고리즘과 같이 최소 우선순위 큐를 어떻게 구현하느냐에 달려있습니다.

내용이 완전히 같으므로 여기를 참고해주세요 !

이상으로 Dijkstra's 알고리즘을 알아보았습니다.

Dijkstra's 알고리즘은 최소 우선순위 큐를 사용하여, 값이 작은 정점을 하나씩 뽑아 인접 간선들에 대해 Relax를 수행하여 SSP를 구현합니다.

동작 방식은 Prim's 알고리즘과 유사하지만, 완전히 같지는 않습니다.