최단 경로 알고리즘

가중치 그래프에서 두개의 노드를 잇는 가장 짧은 경로를 찾는 문제

즉 가중치의 합이 가작 작은 경로 찾기

종류

• 단일 출발 (single-source) 최단 경로 문제
  • 그래프 내 특정 노드에서 출발해서 그래프 내 모든 다른 노드에 도착하는 가장 짧은 경로
• 단일 도착 (single-destination) 최단 경로 문제
  • 모든 노드로 출발해서 그래프 내 특정 노드로 도착하는 가장 짧은 경로를 찾는 문제
• 단일 쌍 (single-pair) 최단 경로
• 전체 쌍 (all-pair)최단 경로

다익스트라 문제는 종류중에 단일출발 최단 경로 문제에 적합

다익스트라 알고리즘 로직

방향이 있는 가중치 그래프다

거리 저장을 미리 A에서 출발이라면 A = 0 나머지는 inf 로 셋팅

우선순위 큐(최소힙)을 이용해서

BFS 간선의 가중치 모두 1

다익스트라 간선의 가중치 ≥ 0 한 정점에서 모든정점까지

A* 한정점 ~ 한정점 ..!?

다익스트라 알고리즘

Input

• graph G(V,E) := Nonnegative-Weighted Graph
• Start Vertex S / Vertices {S1, ….. }

output

• 시작점에서 모든 점 까지의 최단거리

Time Complexity

• O(E log V)

dist[i] = 시작점에서 i번 정점까지 가능한 최단 거리

자료구조 D := {(v,d) | 시작점에서 v까지 d만에 갈 수 있음을 확인했다}

1. dist 배열 초기화 (S,0)을 D에 저장
2. dist[i] = 0 if i == S else inf
3. min(v,d) D안에서 추출
4. dist[v] < d → v까지의 최단거리보다 d가 크다면, 이미 가치가 없는 정보이므로 폐기
5. v,d를 통해 새로운 정보를 D에 추가
6. b+c < dist[w] → dist[w] =a +c (w,d+c)