최단 경로(Shortest Path)
주어진 가중치 그래프에서 출발점으로부터 도착점까지의 최단경로를 찾는 문제
최단 경로란, 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로로 일반적으로 시작점과 끝점이 존재한다.
유형
one-to-one, single-pair
하나의 정점에서 다른 하나의 정점까지의 최단경로 문제
one-to-all 알고리즘을 사용, 원하는 정점에 도달하면 중지하는 방식으로 구현
one-to-all, single-source
하나의 정점에서 다른 모든 정점까지의 최단경로 문제
Dijkstra, Bellman-Ford
all-to-one, single-destination
하나의 목적지로 가는 모든 최단경로 문제
무방향 그래프 : single-source와 동일한 방식 적용
유방향 그래프 : 목적지로 가는 모든 노드의 방향을 반대로 변경 후, single-source방식을 적용
all-pairs
모든 최단경로를 구하는 문제
Floyd-warshall
그래프는 $G(V,E)$로 나타낸다. 여기서 $V$와 $E$는 각각 정점(vertex, node)과 간선(edge)의 집합이다.
Dijkstra(다익스트라)
주어진 출발점으로부터 모든 정점까지의 최단거리 및 경로 계산이 가능하다.
출발 정점으로부터 BFS(너비우선탐색)를 통해 이웃한 정점을 방문한다.
- 방문할 때마다 해당 정점까지 가는데 방문한 경로와 간선의 가중치를 합해서 저장
- 이미 방문한 정점에 다시 방문한 경우, 기존에 저장된 가중치 합과 현재 가중치를 비교하여 더 작은 값을 저장한다.
음수 가중치가 존재하는 경우 사용할 수 없다.
Prim 알고리즘과 원리가 유사, Greedy 알고리즘 기반 또는 DP이기도 하다.
기본 알고리즘의 시간복잡도는 $O(V^2)$이다
우선순위 큐를 사용한 경우, 시간복잡도는 $O(E\log V)$다.
우선순위 큐를 사용하는 경우, 두 단계를 거치게 된다.
1번째로는 각 정점마다 인접한 간선들을 모두 검사하는 작업$(O(E))$이고,
2번째로는 우선순위 큐에 원소를 넣고 삭제하는 작업$O(E\log E)$이다.
Bellman-Ford(벨만 포드)
- 주어진 출발점으로부터 모든 정점까지의 최단거리 및 경로 계산이 가능하다.
- 간선의 가중치 중 음수가 존재하더라도 사용할 수 있는 알고리즘이다.
- 대신 음수 사이클(negative cycle)은 존재하지 않아야 한다.
- V개의 정점과 E개의 간선이 주어졌을 경우, V-1번만큼 E개의 간선을 탐색하여 최단거리를 갱신한다.
- 시간 복잡도는 $O(EV)$로 다익스트라 알고리즘보다 느리다.
Floyd-warshall(플로이드 워셜)
- 그래프 상의 모든 노드에서부터 최단 경로 찾기, 즉 시작 노드가 다수로 모든 정점 쌍에 대한 최단경로를 구하는 알고리즘이다.(All Pairs Shortest Paths)
- 워셜의 유항그래프의 정점들 간 상호 연결 경로의 존재 여부 판정을 위한 알고리즘에서 변형되었다.
- 정점이 $N$개 라면, 구해야 할 최단 경로의 수가 자신의 경로까지 포함한 $N^2$ 개다.
- 본질적으로 알고리즘은 Dijkstra와 같은 개념으로 출발점을 0부터 N-1개로 바꾼 Dijkstra 알고리즘을 적용하여 DP의 원리를 이용한다.
- 간선의 가중치가 음수인 경우도 가능하나 음수사이클(negative cycle)은 존재하지 않아야 한다.
- 음수사이클의 여부를 판단하기 위한 용도로도 사용한다.
- 시간 복잡도는 $O(V^3)$로 노드가 적고 모든 정점의 최단거리를 구할 때 유용하다.