Algorithm) 다익스트라(Dijkstra) 알고리즘

다익스트라(Dijkstra)

다익스트라 알고리즘은 대표적인 최단 경로 탐색 알고리즘! 
다익스트라 알고리즘을 사용하면 한 정점에서 다른 모든 정점으로 가는 최단 경로를 알 수 있습니다. 이때 모든 간선의 가중치는 음수이면 안됩니다 (간선의 가중치에 음수가 포함되어 있으면 벨만-포드 알고리즘을 사용할 수 있습니다)

 

다익스트라를 구현하는데는 최단 거리를 저장할 배열과 우선순위 큐 두개가 필수적입니다.

 

예시와 함께 볼게요

 

https://babbab2.tistory.com/110

A	B	C	D	E	F
0	inf	inf	inf	inf	inf

최단 거리 배열을 만들고 우선 시작점은 0 나머지는 inf(무한대)로 초기화해줍니다.

그리고 순위 큐에 시작점을 넣어줍니다

A

0

우선 순위 큐에서 맨 앞에 있는 노드를 추출하고 해당 노드에서 갈 수 있는 노드들을 우선 순위 큐에 넣어주고 

최단 거리 배열을 업데이트 해줍니다. 

A	B	C	D	E	F
0	9	1	15	inf	inf

A -> B = 9

A -> C = 1

A -> D = 15

 

우선 순위 큐는 요렇게 되겠네요

C	B	D
1	9	15

이제부터는 방금 작업을 우선 순위 큐가 빌때까지 반복해줍니다

1. 우선 순위 큐에서 맨 앞 노드를 추출

2. 해당 노드에서 갈 수 있는 노드들을 우선 순위 큐에 넣어준다

3. 최단 거리 배열 업데이트

 

우선 순위 큐에서 C 노드가 가장 앞에 있네요

A	B	C	D	E	F
0	6	1	15	4	inf

그래프를 보시면 C에서 갈 수 있는 노드는 B, E입니다

E는 처음으로 갈 수 있는 노드가 되었으므로 C까지의 최단 거리 + C -> E인 4를 넣어줍니다

그리고 B는 A에서 갈 수 있었는데 거리가 9였습니다. 하지만  C를 거치면 1 + 5 로  6에 갈 수 있게 되었습니다. 우리가 찾는것은 최단 거리이므로 최단 거리 배열을 업데이트 해줍니다. 

우선 순위 큐는 이렇게 되겠죠?

E	B	B	D
4	6	9	15

 계속 반복해주면 최종적으로

A	B	C	D	E	F
0	6	1	15	4	11

이런 그래프를 얻을 수 있게된답니다

 

다익스트라 알고리즘의 시간 복잡도는 간선의 개수를 E라고 했을 때

1. 노드마다 인접한 간선을 모두 검사하는 과정 = 𝑂(𝐸)

2. 우선순위 큐에 enqueue, dequeue하는 과정 = 𝑂(𝑙𝑜𝑔𝐸)

그래서 총 시간 복잡도는 𝑂(𝐸𝑙𝑜𝑔𝐸)!

 

참고 

https://babbab2.tistory.com/110