1. 개요
그래프 상에서 정점과 정점 간의 최단 거리를 구하는 문제.기업 인적성검사 문제 유형으로도 이따금씩 출제되기도 한다.
2. 관련 알고리즘
- 너비 우선 탐색: 비가중치 그래프 상에서 단일 소스로 부터 다른 정점까지의 최단 경로를 구하는 알고리즘
- 다익스트라 알고리즘: 음의 가중치가 존재하지 않는 가중치 그래프 상에서 단일 소스로 부터 다른 정점까지의 최단 경로를 구하는 알고리즘
- 플로이드-워셜 알고리즘: 음의 가중치가 존재하지 않는 가중치 그래프 상에서 모든 정점간의 최단 경로를 구하는 알고리즘
- 벨만-포드 알고리즘: 음의 사이클이 존재하지 않는 가중치 방향성 그래프 상에서 모든 정점간의 최단 경로를 구하는 알고리즘