최단경로 알고리즘

최단경로: 간선의 가중치가 있는 두 정점사이의 경로들 중에 간선의 가중치의 합이 최소인 경로

- 하나의 시작 정점(고정)

  1. 다익스트라: 음의 가중치 X

  2. 벨만포드: 음의 가중치 O

 

도착점 도착시 가중치의 합으로 비교해야 한다. 모든 경로를 확인한다.

 

Dijkstra

- 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로 구하는 방식

- 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다.

s: 시작 정점, A: 인접 행렬, D: 시작 정점에서의 거리
V: 정점 집합, U: 선택된 정점 집합

Dijkstra(s, A, D)
	U = {s};
    
    FOR 모든 정점 v
    	D[v] = A[s][v]
        
    WHILE U != V
    	D[w]가 최소인 정점 w 왼쪽 포함 V-U를 선택
        U <- U 합집합 {w}
        FOR w에 인접한 모든 미방문 정점 v
        	D[v] = min(D[v], D[w] + A[w][v])

1. 모두 무한대

2. 출발지는 0

3. 출발지와 연결된 아이들 거리 (이미 저장된 것보다 작을 경우) D 업데이트 

4. 고려된 출발지 true

5. 한번 고려된 정점은 다익스트라 상 더 작아질 수 없다. 그러니 고정한다.(경유지로 탐색된 애는 앞으로 건들지 않는다.)

반복

6. 고려된 정점들 사이에서 최소값 찾아서 경유하기

7. 경유할 거리 D 업데이트

6. 경유지로 고려된 정점이 도착지면 완료

 

S는 출발지에서 자신으로 오는 최소 비용