1. 개요
그래프 상에서 정점과 정점 간의 최단 거리를 구하는 문제.기업 인적성검사 문제 유형으로도 이따금씩 출제되기도 한다.
2. 관련 알고리즘
- 너비 우선 탐색: 비가중치 그래프 상에서 단일 소스로 부터 다른 정점까지의 최단 경로를 구하는 알고리즘
- 다익스트라 알고리즘: 음의 가중치가 존재하지 않는 가중치 그래프 상에서 단일 소스로 부터 다른 정점까지의 최단 경로를 구하는 알고리즘
- 플로이드-워셜 알고리즘: 음의 가중치가 존재하지 않는 가중치 그래프 상에서 모든 정점간의 최단 경로를 구하는 알고리즘
- 벨만-포드 알고리즘: 음의 사이클이 존재하지 않는 가중치 방향성 그래프 상에서 모든 정점간의 최단 경로를 구하는 알고리즘
- 2025년 칭화대 연구진이 개발한 알고리즘: 다익스트라 알고리즘과 벨만 포드 알고리즘을 조힙하여 다익스트라 알고리즘의 O(m+n log(n))을 O(m log^(2/3)(n))으로 개선하였다. 간선의 개수(m)가 정점개수(n)보다 훨씬 크다면 더 느릴수도 있긴 하다.