[알고리즘] 최단 경로

최단 경로

• 조건

– 간선 가중치가 있는 유향 그래프

– 무향 그래프는 각 간선에 대해 양쪽으로 유향 간선이 있는 유향 그래프로 생각할 수 있다

• 즉, 무향 간선 (u, v)는 유향 간선 (u, v)와 (v, u)를 의미한다고 가정하면 된다

• 두 정점 사이의 최단경로

– 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로

– 간선 가중치의 합이 음인 싸이클이 있으면 문제가 정의되지 않는다

 

• 단일 시작점 최단경로

– 단일 시작점으로부터 각 정점에 이르는 최단경로를 구한다

다익스트라 알고리즘 : 음의 가중치를 허용하지 않는 최단경로

벨만-포드 알고리즘 : 음의 가중치를 허용하는 최단경로

싸이클이 없는 그래프의 최단경로

 

• 모든 쌍 최단경로

– 모든 정점 쌍 사이의 최단경로를 모두 구한다

플로이드-워샬 알고리즘

 

다익스트라 알고리즘

완성된 부분만을 거쳐서 노드까지 오는 경로 중 가장 짧은 것을 선택한다.

Dijkstra(G, r) 
# G=(V, E): 주어진 그래프 
# r: 시작으로 삼을 정점 
{ 
	S ← Ф ;  # S : 정점 집합 
	for each u∈V 
		d[u] ← ∞ ; 
	d[r] ← 0 ; 
	while (S≠V){ # n회 순환된다 
		u ← extractMin(V-S, d) ;
		S ← S ∪{u}; 
		for each v∈L(u) # L(u) : u로부터 연결된 정점들의 집합 
			if (v∈V-S and d[u] +w[u, v] < d[v] ) then { # 갱신되는 값이 있으면 
				d[v]  ←  d[u] + w[u, v]; # 갱신한다
				prev[v]  ←  u;  # 나를 바꿔준 은인 정점 집합
        	} 
} 

extractMin(Q, d[]) 
{ 
        집합 Q에서 d값이 가장 작은 정점 u를 리턴한다 ;
} 
# 모든 간선의 가중치는 음이 아니어야 함
# O(|E|log|V|)

 

플로이드 워셜 알고리즘

만약 i = 1, j = 4, k = 3이라면 정점1에서 정점4까지 정점0~3에 속하는 것만 거쳐서 갈 수 있는 최단 경로.

이 슬라이드에서 말하는 문제의 총수는 3중 for문에 대한 설명입니다. 모든 K에 대해서 모든 i에 대해서 모든 j에 대해서 고려해야 하므로 문제의 총수가 V^3이란 뜻입니다. 

각 문제를 해결하는데 O(1) 걸린다는 뜻은 이 라인을 한번 계산하는 데에 상수시간이 걸린다는 뜻입니다. 

 

[문제]

 

초기상태

k = 2

k = 4

 

 

 

 

자료참조 - 쉽게 배우는 알고리즘 · 관계 중심의 사고법 / 문병로