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

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

다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 
각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다.

 

초기 모델은 O(V^2)의 시간복잡도를 가졌다. 

이후 우선순위 큐 등을 이용한 고안된 알고리즘이 탄생했고, 현재는 O((V+E)log V)의 시간복잡도를 가지고 있다

(만일 연결 그래프라면 O(ElogV)까지 시간 복잡도를 줄일 수 있다고 한다). 

 

일반적으로는 그래프가 희소 그래프인 경우에 우선순위 큐를 이용하는 것이 낫다고 한다.

 

※ 음의 가중치를 가지면 안되는 이유는

1. 최소 비용의 음의 무한대 발산 

2. 그리디 알고리즘 적용 불가능 : 최적의 해를 보장할 수 없음

  

 

※ 연결 그래프 : 모든 두 꼭짓점 사이에 경로가 존재하는 그래프.

 

※ 희소 그래프 : 밀집 그래프의 반대. 밀집 그래프란, 간선의 수가 최대에 가까운 그래프를 만한다.

   보통, 간선의 총 개수가 정점의 개수^2과 근사하다면 밀집 그래프이다. 

 

 

다익스트라 알고리즘의 매커니즘

다익스트라 알고리즘은 기본적으로 그리디 알고리즘이자 다이나믹 프로그래밍 기법을 사용한 알고리즘이다.

다익스트라 알고리즘은 기본적으로 아래 두 단계를 반복하여 임의의 노드에서 각 모든 노드까지의 최단거리를 구한다.

임의의 노드에서 다른 노드로 가는 값을 비용이라고 한다.

 

1. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다 : 그리디 알고리즘
2. 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다 : 다이나믹 프로그래밍

---

 

A노드에서 출발하여 F노드로 가는 최단 경로를 구하는 문제를 다익스트라 알고리즘을 적용하여 생각해보자.

 

초기화 단계

방문하지 않은 노드 중 가장 비용이 적은 대상 노드는 어디일까?

A노드에서 다른 간선으로 가는 비용이 0인 간선이 존재하지 않는다면, 당연히 A노드일 것이다. 

또한, 그러한 값이 존재한다고 하더라도 첫 번째 단계에서는 'A노드에서 A노드로 가는 지점이 가장 짧다'라고 그냥 정의하고 시작한다.

즉, 첫 번째 단계에서는 가장 비용이 적은 노드를 선택할 기준이 없기 때문에 출발지인 A노드 자신을 초기 선택 노드로 초기화한다.

 

알고리즘 적용

앞서 언급한 두 가지 논리를 그냥 반복해서 적용한다.

위 상태에서 방문하지 않은 노드 중 가장 비용이 적은 대상 노드는 어디 인가? 당연히 A노드이다. 

또한, A노드를 기준으로 갈 수 있는 인접 노드로의 최소 비용은 얼마일까? 결과는 아래와 같을 것이다.

 

 

A 노드 방문 완료

앞선 단계를 그냥 계속 반복하면 된다. 

현재 상태에서 방문하지 않은 노드 중 가장 비용이 적은 노드는 어디 인가?

A노드는 방문 하였기 때문에 B노드가 될 것이다.

 

따라서 B노드를 방문하고, B노드와 인접한 노드들의 최소 비용을 갱신해주면 된다.

 

B노드에서 C노드로 가는 비용은 9이다. 하지만 이미 C노드로가는 최소 비용이 5이므로 갱신할 필요가 없다.

B노드에서 F노드로 가는 비용은 아직 모르므로, 최초 방문 값인 12로 설정해 주었다.

 

이제는 A노드와 B노드를 방문하였기 때문에, 그 중에서 가장 비용이 적은 노드인 D를 선택하고 방문한 뒤

같은 과정을 진행해주면 된다.

 

D노드를 거쳐 C노드로 가는 비용은 4이고, 현재까지 C노드로 가는 최소 비용이 5였기 때문에, D[C]를 4로 갱신할 수 있다.

이전 단계와 마찬가지로, E노드로가는 비용은 미정이었기 때문에 최초 방문 값인 10으로 설정할 수 있다.

그 다음으로 선택된 노드는 C이고,

C노드에서 E노드로 가는 값과 F노드로 가는 값은 각각 기존 E노드나 F노드로 가는 비용보다 모두 작다.

따라서 각 값을 갱신할 수 있다.

그 다음으로 선택된 노드는 E이고, E노드에서 F노드로 가는 비용은 기존 F노드로 가는 비용보다 작다.

따라서 그 값을 갱신해 주었다.

 

마지막으로 방문해야하는 노드인 F에서는 더 이상 갈 수 있는 노드가 존재하지 않으므로,

방문만 완료하고 알고리즘을 종료해주면 된다.

모든 노드 방문 완료.

 

 

https://sskl660.tistory.com/59

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