Shortest Path Problem(최단거리 문제)

Shortest Path Problem(최단 경로 문제)

• 정점 u 에서 v까지의 최단 경로 : 정점 u에서 정점 v까지의 경로 중에 경로의 값이 가장 작은 경로
• 정점 u를 시작점(source), 정점 v를 도착점(destination) 이라고 한다. 
• δ(u,v) : u에서 v까지의 최단 경로 값
• negative-weight cycles이 있으면 최단경로 문제는 정의되지 않는다. δ(u,v)=-∞가 나올 수 있음
• positive-weight cycles, zero-weight cycles 는 구할 수 있다. (사이클 무시하면 됨)
• optimal substructure theorem(최적부분 구조 : 분할된 문제의 결과가 매번 같다)으로 greedy sub를 만족한다.
• δ(s,v) ≤δ(s,u)+δ(u,v) 가 항상 성립한다. 
• d[v] : 최단거리 추청치. 초기값 : d[v]=∞, d[v]->δ(s,v)
• 𝝅[v] : s에서 v로 갈 때의 전인자. 전인자 없으면  𝝅[v]=NIL(초기값), 𝝅를 이은 트리를 shortest-path tree라고 부른다.
• Relazation : d[v]를 더 줄일 수 있는지 테스트. 즉 더 빠른길이 있는지를 테스트하여 존재하면 값을 변경한다.

 

 

 

 

최단경로 문제의 종류

• Single-Source Single-Destination(1-1) : 시작점 1개 도착점 1개
• Single-Source All-Destination(1-M) : 시작점 1개, 도착점 여러개
• All-Sources Single-Destination(M-1) : 시작점 여러개, 도착점 1개
• All-Sources All-Destinations(M-M) : 시작점 여러개, 도착점 여러개

 

 

Bellman-Ford Algorithm(벨만 포드 알고리즘)

initialization, Relaxation 으로 연산한다.

음의 간선이 있는 경우에도 문제를 해결할 수 있다. 

negative weight cycles가 있는지 없는지 확인하는 작업 필요

간선을 기준으로 진행한다. 

estimate d[v]는 진행될수록 점점 작아진다. 

O(VE)

 

Dijkstra's Algorithm(다익스트라 알고리즘)

initialization, Relaxation 으로 연산한다.

Greedy 알고리즘

매번 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다.

벨만포드보다 빠르다.

음의 간선을 허용하지 않는다. 즉 negative weight cycles를 확인할 필요 없음

노드를 기준으로 진행한다. 각 단계를 시작할 때 가장 작은값을 우선적으로 확인한다.

min priority queue, heap으로 Greedy choice를 구현한다. 

O(ElogV)