최단경로(shortest path problem)-1

최단경로(shortest path problem)

- 가중치(방향) 그래프 G=(V,E), 즉 모든 에지에 가중치가 있음

- 경로 p=(v0,v1,...vk)의 길이는 경로상의 모든 에지의 가중치의 합

- 노드 u에서 v까지의 최단경로의 길이를 S(u,v)라고 표시하자.

최단경로문제의 유형

- Single-source(one-to-all) : 하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾아라. ex)Dijkstra의 알고리즘

- Single-destination : 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾아라./ single-source문제와 동일

- Single-pair(one-to-one) : 주어진 하나의 출발 노드 s로부터 하나의 목적지 노드 t까지의 최단 경로를 찾아라

- All-pairs : 모든 노드 쌍에 대해서 최단 경로를 찾아라.

최단경로와 음수 가중치

최단경로의 기본 특성

- 최단 경로의 어떤 부분경로도 역시 최단 경로이다.

- 최단 경로는 사이클을 포함하지 않는다.(음수사이클이 없다는 가정하에서)

■ Single-source 최단경로문제

기본연산 : Relaxation

- 대부분의 single-source 최단경로 알고리즘의 기본 구조

1. 초기화

2. 에지들에 대한 반복적인 relaxation

- 알고리즘들 간의 차이는 어떤 에지에 대해서, 어떤 순서로 relaxation을 하느냐에 있음

기본알고리즘