다익스트라 알고리즘

728x90

반응형

SMALL

---

최단 경로 문제

그래프 내의 한 정점에서 다른 정점으로 이동할 때 가중치 합이 최소값이 되도록 만드는 경로를 찾는 알고리즘

 

가중 간선 (Edge weight)

간선들이 할당된 값을 가짐

 

가중 경로 (Path Weight)

경로에 속하는 모든 간선의 값을 더한 값

 

만약 가중 간선이 아닌 경우는

간선의 수를 가지고 최단 경로를 구하기도 함

---

 

 

모든 간선 가중치가 음이 아닌 일반적인 경우

다익스트라 알고리즘으로 적용

 

음의 가중치가 존재하는 경우

○ 벨만-포드 알고리즘으로 적용 

○ 음의 가중치는 허용하지만 가중치 합이 음인 사이클은 절대 허용하지 않음

○ 음의 사이클이 존재하면 해당 사이클을 계속 반복한다면 가중치 합이 무한히 작아질 수 있으므로 최단 경로 문제 자체가 성립하지 않음

---

다익스트라 알고리즘

어떠한 간선도 음수값을 갖지 않는 방향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로를 찾아주는 알고리즘

○ 방향 그래프, 무방향 그래프 모두 가능

○ 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 구하는 방법 

 

최소 신장 트리 알고리즘인 프림 알고리즘과 유사

프림 알고리즘이 단순히 간선의 길이를 이용해 어떤 간선을 먼저 연결할지를 결정하는데 반해 다익스트라 알고리즘은 경로의 길이를 감안해서 간선을 연결함

 

모든 노드를 순회해야 하므로 시간복잡도에 결정적인 영향을 미치게 되는데 제대로 구현된 우선순위 큐를 활용하면 비용을 줄일  수 있음

처음 고안한 알고리즘은 O(V^2)의 시간복잡도를 가졌으 나 이후 우선순위 큐(=힙 트리)등을 이용한 더욱 개선된 알고리즘이 나와 O(E logV)의 시간복잡도를 가짐

 

다익스트라 알고리즘은 벨만-포드 알고리즘과 동일한 작업을 수행하고 실행 속도도 더 빠름

다익스트라 알고리즘은 가중치가 음수인 경우는 처리할 수 없으므로 이런 경우에는 벨만-포드 알고리즘을 사용함

---

다익스트라  알고리즘의 응용

가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용됨

○ 내비게이션에서 각 도시들을 정점으로, 도로들을 간선으로 갖는 그래프로 간주한다면 두 도시를 잇는 가장 빠른 길을 찾는 문제

○ 미로 탐색 알고리즘으로 사용할 수 있음

○ 라우팅에서도 IP 라우팅 프로토콜의 한 종류인 OSPF 방식의 프로토콜에서 사용

---

다익스트라 알고리즘 적용 방법

① 각 정점 위에 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 모든 정점 위에 있는 경로의 길이를 ∞(무한대)로 초기화함 

② 시작 정점의 경로 길이를 0으로 초기화하고(시작 정점에서 시작 정점까지의 거리는 0이기 때문) 최단  경로에 추가함 

③ 최단 경로에 새로 추가된 정점의 인접 정점들에 대해 경로 길이를 갱신하고 이들을 최단 경로에 추가함, 만약 추가하려는 인접 정점이 이미 최단 경로안에 존재한다면 갱신되기 이전의 경로 길이가 새로운 경로의 길이보다 더 큰 경우에 한해 다른 선행 정점을 지나던 기존의 경로를 현재 정점을 경유하도록 수정함

④ 그래프 내의 모든 정점이 최단 경로에 소속될 때까지 ③ 과정을 반복함

---

---

---