그래프 (Graph) - 최단 경로 (Dijkstra, Ford 알고리즘)

최단 경로

가중치 graph, 출발점(source), 종점(destination), 방향 graph

 

전제 조건

방향 그래프 G = (V, E)

n개의 정점

G의 간선에 대한 가중치 함수 lengt(i, j)

출발점 v

 

 

문제점

1. 단일 출발점 / 모든 종점 (간선의 길이가 양수인 경우)

    

    ex ) 

간선 비용 (length)	최단 경로 비용 (dist)

 

Dijkstra 알고리즘 - 비용

모든 가중치가 양수일때만 적용 가능

 

단계

① S = 출발점 v를 포함하여 이미 최단 경로가 발견된 정점들의 집합

② S에 속하지 않는 정점들 중 dist 값이 최소인 정점 u 선택, 이는 S의 원소가 됨

③ S에 속하지 않는 정점들에 대해 새로운 최단 경로가 존재하는 경우, 해당 정점에 대한 dist 값 갱신

    즉, dist[w] = min { dist[w], dist[u] + length[u,w] } ( w $\notin$ S )

④ S에 n-1개의 정점이 포함될 때까지 n-2번 반복

 

dyeoma.tistory.com/31

Dijkstra 알고리즘

Dijkstra 알고리즘 - 경로

일차원 배열 path를 역추적

최단 경로 비용 (dist)	최단 경로 (path)
	????????

 

 

2. 모든 쌍의 최단 경로

   서로 다른 정점의 쌍 u와 v 간의 최단 경로 길이 (음수 길이 cycle 존재하지 않을 때)

   즉, A(i, j)가 정점 i로부터 j까지의 최단 경로의 길이인 행렬 A 결정

 

방법

① 각 정점을 출발점으로 하여 Dijkstra 알고리즘 n번 적용

② 동적 프로그래밍 적용 - Ford 알고리즘

 

두 방법 모두 시간 복잡도는 O($n^3$)으로 같으나, 실제 소요시간은 ②이 더 빠르다

 

 

Ford 알고리즘

원리

i에서 j로의 최단 경로에서, k가 이 최단 경로 상 중간에 있는 점이라면

i에서 k로의 부분 경로와 k에서 j로의 부분 경로가 각각 최단 경로

 

$A^k(i, j)$ = 0~k번째 정점만 통과하는 i에서 j로 가는 최단 경로 길이

$A^{-1}$ = 인접행렬

 

순환식

$A^{-1}(i,j)$ = length(i, j)   (0≤i≤n-1)

 

 

$A^{k-1} → A^k$ 만드는 법

쌍 i, j의 최단 경로가 정점 k를 통과하지 않을 때 : $A^k(i, j) = A^{k-1} (i,j)$

쌍 i, j의 최단 경로가 정점 k를 통과할 때          : $A^k(i, j) = A^{k-1} (i,k) + A^{k-1}(k,j)$

∴ $A^k (i, j) $= min { $A^{k-1} (i,j), A^{k-1} (i,k) + A^{k-1}(k,j)$ }      (0≤k≤n-1)

 

 

ex)

 

 

dyeoma.tistory.com/32

Ford 알고리즘