인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.
최단경로
최단경로문제의 유형
- Single-source :
-
하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾아라.
-
예 Dijkstra의 알고리즘
-
- Single-destination :
-
모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾아라.
-
Single-source 문제와 동일
-
- Single-pair :
-
주어진 하나의 출발 노드 s로 부터 하나의 목적지 노드 t까지의 최단 경로를 찾아라
-
최악의 경우 시간복잡도에서 Single-source 문제보다 나은 알고리즘이 없음
-
- All-pairs :
- 모든 노드 쌍에 대해서 최단 경로를 찾아라.
최단경로와 음수 가중치
-
알고리즘에 따라 음수 가중치가 있어도 작동하는 경우도 있고 그렇지 않은 경우도 있음
최단경로의 기본 특성
-
최단 경로의 어떤 부분경로도 역시 최단 경로이다.
-
최단 경로는 사이클을 포함하지 않는다.(음수 사이크링 없다는 가정하에서)
Single-source 최단경로문제
기본 연산: Relaxation
Single-source 최단경로
기본 알고리즘
즉, n-1번의 반복으로 충분하다.
Bellman-Ford 알고리즘
