최단경로 알고리즘

최단경로란

최단경로 알고리즘은 가중 그래프에서 출발점부터 목적점까지 가중치 합이 최소인 경로를 찾는다.

지도 앱이 가장 짧은 길을 찾는 원리가 바로 이것이다.

이 영상에서는 대표 알고리즘 네 가지를 차례로 비교한다.

대표 알고리즘 네 가지

네 알고리즘은 음수 간선 허용 여부와 문제 형태로 구분한다.

다익스트라는 음수 간선이 없는 단일 출발 최단경로를 구한다.

벨만-포드는 음수 간선을 허용하고 음의 사이클을 검출한다.

플로이드-워셜은 모든 쌍의 최단경로를 구하고, A*는 목적지 쪽으로 탐색한다.

완화 연산

모든 알고리즘은 완화 연산을 공통으로 쓴다.

간선 (u, v)를 지날 때 비용이 줄면 dist[v]를 갱신한다. 이를 완화라 한다.

이 식을 반복하면 최단 거리가 확정된다. 원리는 최적 부분구조다.

계산 예제

계산 예제는 가정한 그래프에서 출발지 A, 목적지 E의 최단 거리를 구한다.

A에서 B는 4, C는 2로 갱신된다. 가장 가까운 C를 먼저 확정한다.

C를 거쳐 B는 3, D는 5, E는 10으로 갱신된다.

D 5를 확정하면 E는 7로 줄어든다. 최종 최단 거리는 7이다.

다익스트라와 A* 비교

앞 문제의 답은 7이다.

다익스트라와 A*는 둘 다 음수 간선이 없는 그래프에서 쓴다.

차이는 A*가 목적지까지의 추정값 h(n)을 더해 탐색 방향을 좁힌다는 점이다.

h(n)이 실제 잔여 거리를 넘지 않는 허용 가능한 휴리스틱이어야 최단경로가 보장된다.

헷갈리는 점

시험에서 자주 틀리는 부분은 음수 간선 처리와 조건 확인이다.

음의 가중치가 있으면 다익스트라 대신 벨만-포드를 쓴다.

벨만-포드는 음의 사이클 판정 절차를 빠뜨리면 감점된다.

A*는 h(n)이 허용 가능한지 반드시 확인해야 한다.

정리

정리하면 음수 간선 유무와 목적지 정보, 모든 쌍 필요 여부로 알고리즘을 고른다.

음의 가중치면 벨만-포드, 목적지가 있으면 A*를 떠올린다.

직접 풀어 보자.