그래프 – 최단 경로 알고리즘

최단 경로 문제는 무엇입니까?

두 노드 사이의 최단 경로를 찾는 문제

목표는 가중 그래프에서 에지의 가중치 합을 최소화하는 경로를 찾는 것입니다.

문제 유형

단일 출발 및 단일 도착

그래프의 특정 노드 u에서 다른 특정 노드 v까지의 최단 경로를 찾는 문제

단일 시작

그래프의 특정 노드 u에서 그래프의 다른 모든 노드까지의 최단 경로를 찾는 문제입니다.
* 시작점이 A라면 A가 아닌 다른 노드 사이의 최단경로를 찾는 것을 의미
* 다익스트라 알고리즘여기에 적용

올 페어

그래프에서 모든 노드 쌍(u, v)에 대한 최단 경로를 찾는 문제입니다.