최단 경로 알고리즘
최단 경로 정의
- 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
하나의 시작 정점에서 끝 정점까지의 최단 경로
- 다익스트라(Dijkstra) 알고리즘
- 음의 가중치를 허용하지 않음
- 벨만-포드(Bellman-Ford) 알고리즘
- 음의 가중치 허용
모든 정점들에 대한 최단 경로
- 플로이드-워샬(Floyd-Warshall) 알고리즘
Dijkstra 알고리즘
시간복잡도 Prim이랑 동일
- 시작 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
- 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.
- 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다.
s: 시작 정점, A: 인접 행렬, D: 시작정점에서의 거리 V: 정점 집합, U: 선택된 정점 집합 Dijkstra(s, A, D) U = {s}; FOR 모든 정점 v D[v] <- A[s][v] // 간선 없는 애들은 INF WHILE U != V // 선택된 정점의 집합이 모든 정점이 아니면 D[w]가 최소인 정점 w ∈ V-U를 선택 // 처리되지 않은 정점중 출발지에서 자신으로 오는 비용이 최소인 정점을 찾음 U <- U ∪ {w} FOR w에 인접한 모든 미방문 정점 v D[v] <- min(D[v], D[w] + A[w][v]) // 선택한 정점 w를 거치는것이 가까운지 확인
Dijkstra with Priority Queue
- D[w]가 최소인 정점 w ∈ V-U를 선택 // 처리되지 않은 정점중 출발지에서 자신으로 오는 비용이 최소인 정점을 찾음
- 이 부분을 PQ로 대체