그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제.

가중치가 없는 그래프에 대한 최단 경로는 너비 우선 탐색

이 알고리즘들은 최단 경로를 구성하는 정점들의 목록을 구해 주는 것이 아니라 최단 경로의 길이를 찾아 줄 뿐이다.

문제 구분

• 음수 간선이 있는가 → 음수 사이클이 생길 수 있기 때문이다.
• 단일 시작점 또는 모든 쌍
• 방향 그래프와 무방향 그래프

/// 음수 간선이 있는 무방향 그래프에 대해서는 항상 최단 경로 문제를 제대로 풀 수 없다고 한다.

다익스트라

벨만-포드

플로이드 워셜

가중치 없는 무방향 그래프에서 음수 간선 아닐 때 사이클 구할 수 있음 = DFS

사이클