[그래프] 최단 경로 문제

📌 최단 경로 문제란?

정의

가장 짧은 경로에서 두 꼭짓점을 찾는 문제를 의미한다.
가중 그래프에서 구성하는 변들의 가중치 합이 최소가 되도록 경로를 찾는 문제를 의미한다.
즉 출발 지점에서 도착 지점으로 가는 모든 경로들 중에 최소가 되도록 하는 경로를 찾는 문제를 뜻한다.

예시

도로 지도 상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾아라.
각 도로 구간에서 걸리는 시간 → 변의 가중치

분류

단일-출발 최단 경로 문제

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

단일-도착 최단 경로 문제

모든 꼭짓점들로부터 출발하여 그래프 내의 한 단일 꼭짓점(v)으로 도착하는 가장 짧은 경로를 찾는 문제이다.
이 문제에서 그래프 내의 꼭짓점들을 거꾸로 뒤집으면 출발 최단 경로 문제로 바뀔 수 있다.

전체-쌍 최단 경로 문제

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

대표적인 알고리즘

다익스트라 알고리즘 : 단일-쌍, 단일-출발, 단일-도착 최단 경로 문제를 풀 수 있다.
벨만-포드 알고리즘 : 변의 가중치가 음수라면 단일 출발 문제를 풀 수 있다.
A* 탐색 알고리즘 : 탐색 속도를 높히기 위한 휴리스틱 방법을 사용하며, 단일-쌍 최단 경로 문제를 풀 수 있다.
플로이드-와샬 알고리즘 : 전체-쌍 최단 경로 문제를 풀 수 있다.

📌 참고 자료

TOP