최단 경로 문제

최단 경로 문제란?

그래프에서 최단 경로 문제는 두 노드를 잇는 가장 짧은 경로를 찾는 문제이다.

일반적으로 가중치가 있는 그래프에서는 간선의 가중치 합이 최소가 되도록 하는 문제이다.

 

단일-출발(single-source) 최단 경로

단일 꼭짓점 v에서 출발하여 그래프 내의 다른 꼭짓점들에 도착하는 가장 짧은 경로를 찾는 문제

 

단일-도착(single-destination) 최단 경로 문제

모든 꼭짓점들로부터 출발하여 그래프 내의 단일 꼭짓점 v로 도착하는 가장 짧은 경로를 찾는 문제

 

단일 쌍(single-pair) 최단 경로 문제

주어진 꼭짓점 u와 v에 대해 u에서 v까지의 최단 경로를 찾는 문제

 

전체-쌍(all-pair) 최단 경로 문제

그래프 내의 모든 꼭짓점 쌍들 사이의 최단 경로를 찾는 문제이다.

 

해결할 수 있는 알고리즘

다익스트라 알고리즘 : 단일-쌍, 단일-출발, 단일-도착 최단 경로 문제를 풀 수 있다.

벨만-포드 알고리즘 : 변의 가중치가 음수라면 단일 출발 문제를 풀 수 있다.

A* 탐색 알고리즘 : 탐색 속도를 높히기 위한 휴리스틱 방법을 사용하며, 단일-쌍 최단 경로 문제를 풀 수 있다.

플로이드-와셜 알고리즘 : 전체-쌍 최단 경로 문제를 풀 수 있다.

 

단일 출발 문제

간선의 가충치가 음인 것이 존재하지 않는다면 다익스트라, 아니라면 벨만-포드 알고리즘을 사용해야 한다.

 

다익스트라 알고리즘

출처 : Dijkstra’s Shortest Path Algorithm in Java, easy in 5 minutes

다익스트라 알고리즘은 시작점에서 다른 점까지 가는 최단 거리를 구한다.

10이라는 점에서 모든 정점(20, 30, 40)으로 가는 거리를 구한다고 생각해보자.

 

	10	20	30	40
10	0	∞	∞	∞

초기값을 위와 같이 세팅한다. 10에서 10으로 가는 최단 거리는 당연하게 0에 해당한다. 그 외의 정점과의 거리는 아직 알수 없다.

다익스트라는 기본적으로 큐에서 진행된다. (해당 작업을 priorityQueue를 사용하게 되면 시간 복잡도가 줄어든다)

 

Step1.

먼저 10과 연결된 20, 40를 큐에 넣는다. 그리고 이전 연결 거리와 비교하여 더 짧은 경로로 바꿔준다.

	10	20	30	40
10	0	min(∞, 3) = 3	∞	min(∞, 1) = 1

 

Step2.

이제 40에 각각 연결된 정점을 넣어준다.

40에 연결된 정점 10, 20, 30이 큐에 들어간다.

이때 10의 최단 거리는 0이고, 10-40-10의 경로로 방문한 거리는 1이다. 더 짧은 거리는 10에서 10으로 이동한 거리 0이므로 정점 10은 pop된다. 이러한 방식으로 최단 거리를 갱신한다.

	10	20	30	40
10	min(0, 1) = 0	min(3, 1 + 5) = 3	min(∞, 1 + 7) = 8	1

 

Step3.

이제 20에 각각 연결된 정점을 넣어준다.

20에 연결된 정점 10, 30, 40이 큐에 들어간다.

	10	20	30	40
10	min(0, 3) = 0	3	min(8, 3+4) = 7	min(1, 3+5) = 1

 

Step4.

이제 30에 각각 연결된 정점을 넣어준다.

30에 연결된 정점 20, 40이 큐에 들어간다.

	10	20	30	40
10	0	min(3, 7 + 4) = 3	7	min(1, 15) = 1

 

 

 

참고 자료

ko.wikipedia.org/wiki/최단_경로_문제

ratsgo.github.io/data%20structure&algorithm/2017/11/25/shortestpath/