114. Shortest Path

최단 경로(Shortest Path)는 그래프에서 정점과 정점 사이의 경로 중 길이가 가장 짧은 것을 의미하며 그래프 이론에서 기본적인 내용으로 많이 다루어지는 주제이다. 일반적으로 최단 경로를 찾는 대상은 그래프의 정점으로, 트리에서의 최단 경로는 복잡한 요소가 없기 때문에 최단 경로라는 주제로 따로 분리하지 않는다. 아래의 내용이 끝이다.

• 가중치가 음수인 간선이 하나라도 있다면 그 간선을 무한히 왕복하는 것이 가능하므로 모든 최단 경로의 길이가 $-\infty$가 되며, 가중치가 음수인 간선이 없다면 두 정점 사이의 단순 경로가 두 정점 사이의 최단 경로와 같다.

그래프는 두 정점 사이에 여러 경로가 존재할 수 있으므로 최단 경로를 구하는 것이 더 흥미로운 주제가 된다. 그래프에서 최단 경로를 구하는 알고리즘은 목적에 따라 몇 가지로 나누어지며, 하나씩 차례로 살펴볼 것이다.

• 다익스트라 알고리즘(Dijkstra's Algorithm)은 한 정점에서 모든 정점으로의 최단 경로를 구할 때 많이 사용되는 알고리즘이며 가중치가 음수인 간선이 없을 때만 정상적으로 작동하는 것이 보장된다.
• 벨만-포드 알고리즘(Bellman-Ford Algorithm)은 한 정점에서 모든 정점으로의 최단 경로를 구할 때 사용되는 알고리즘이며 가중치가 음수인 간선이 있어도 잘 작동한다.
• 플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)은 모든 정점에서 모든 정점으로의 최단 경로를 구할 때 사용되는 알고리즘이다.
• SPFA(Shortest Path Faster Algorithm)는 벨만-포드 알고리즘을 변형한 것으로 네트워크 플로우 문제를 풀 때 사용되는 경우가 많다.
• $0$-$1$ BFS는 모든 간선의 가중치가 $0$ 또는 $1$인 그래프에서 사용할 수 있는 최단 경로 알고리즘이다.
• 다이얼 알고리즘(Dial's Algorithm)은 한 정점에서 모든 정점으로의 최단 경로를 구할 때 사용되는 알고리즘으로 간선들의 가중치가 작을 때 효과적이다.

이중 앞의 세 가지가 최단 경로 알고리즘으로 많이 다루어지는 편이며 뒤의 세 가지는 아직은 마이너한 부류에 속한다고 보면 된다.

 

→ solved.ac tag: shortest_path