그래프에서 최단 경로란?
•
그래프에서 최단 경로란 어떤 노드 A에서 어떤 노드 B까지의 최단 경로를 의미한다.
•
즉, A에서 B로 가는 다양한 경로가 있다면 그중에서 거리가 가장 짧은 거리를 최단 거리라 하며 그때의 경로를 최단 경로라고 한다.
•
거리가 짧다는 것의 기준은 무엇일까?
◦
가중 그래프가 아닌 경우에는 경로 상에 있는 간선의 수가 적을수록 짧다.
◦
가중 그래프인 경우에는 경로 상에 있는 간선의 가중치의 합이 작을수록 짧다.
•
최단 경로는 항상 정의될 수 있는가?
◦
사이클이 존재하며, 그 사이클이 음수 사이클이라면 최단 거리가 정의될 수 없다.
▪
왜냐하면, 사이클을 거치면 거칠수록 경로의 거리가 줄어드는 구조이기 때문에 최단 거리가 무한히 작아질 수 있기 때문이다.
•
음수 사이클이 없는 경우에 최단 경로/거리 알고리즘
1.
다익스트라(Dijkstra) 알고리즘
•
제약 조건: 음수 간선 존재 X
•
결과물: 한 노드에서 다른 모든 노드까지의 최단 경로/거리
시간 복잡도:
2.
벨만-포드(Bellman-Ford) 알고리즘
•
제약 조건: 없음
•
결과물: 한 노드에서 다른 모든 노드까지의 최단 경로/거리
시간 복잡도:
3.
플로이드-워셜(Floyd-Warshall) 알고리즘
•
제약 조건: 없음
•
결과물: 모든 노드에서 다른 모든 노드까지의 최단 경로/거리
시간 복잡도:
다익스트라 알고리즘
•
한 노드에서 다른 모든 노드까지의 최단 경로/거리를 구하는 알고리즘이다.
•
다익스트라 알고리즘은 음수 간선이 존재하지 않을 때만 사용할 수 있다.
•
다익스트라 알고리즘은 시작(기준) 노드로부터 가까운 노드를 그리디하게 방문한다.
음수 간선이 존재하지 않는 경우에는 경로가 늘어나면 항상 경로의 길이 또한 늘어나므로, 시작 노드로부터 가까운 노드를 그리디하게 선택하는 전략을 사용해도 되는 것이다.
•
다익스트라 알고리즘 로직
◦
현재 살펴보지 않은 경로 중에서 가장 거리가 짧은 경로를 먼저 살펴봐야 한다.
◦
따라서, 경로들을 heap(priority queue) 자료형에 담고 짧은 경로부터 꺼내서 탐색하면 된다.
시작 노드를 0번 노드로 하여 다익스트라 알고리즘 수행
예제 코드
최단 경로 알고리즘 정리
•
Case1. 한 노드에서 다른 (모든) 노드까지의 최단 경로/거리 (음수 간선 존재 X)
◦
다익스트라 알고리즘
•
Case2. 한 노드에서 다른 (모든) 노드까지의 최단 경로/거리 (음수 간선 존재 O)
◦
벨만-포드 알고리즘
•
Case3. 모든 노드에서 모든 노드까지의 최단 경로/거리
◦
플로이드-워셜 알고리즘