최단경로 요약

요약

• 최단경로 문제는 가중그래프와 두 개의 정점 u와 v가 주어졌을 때 u와 v 사이의 무게의 합이 최소인 경로를 구하는 문제를 말한다.
• 출발정점으로부터 다른 모든 정점에 이르는 최단경로들의 트리가 존재한다. 이를 단일점 최단경로라고 부른다.
• 가중 방향그래프에 음의 무게를 가진 싸이클이 존재한다면 최단경로는 존재하지 않는다. 마찬가지로 가중 무방향 그래프에 음의 무게를 가진 간선이 존재해도 최단경로는 존재하지 않는다.
• 최단경로를 찾는 알고리즘은 그래프의 형태에 따라 선택이 달라진다. 즉, 음의 무게를 가진 간선이 있는지 없는지, 무방향인지 방향인지, 그리고 비싸이클(DAG)인지 아닌지에 따라 최적 알고리즘이 따로 존재한다.
• Dijkstra 최단경로 알고리즘은 탐욕법에 기초하며 음의 무게를 가진 간선이 없는 그래프에 적용된다. 음의 무게를 가진 간선이 존재하는 그래프에 적용할 경우 최단경로를 구한다는 보장이 없다.
• 방향 비싸이클 그래프의 경우 Dijkstra나 Bellman-Ford 알고리즘보다 빨리 최단경로를 구하는 알고리즘이 있다. 이 알고리즘은 위상순서를 이용하며 DAG에 음의 무게를 가진 간선이 있더라도 정확히 작동한다.