최단 경로 문제란?
•
최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제
•
가중치 그래프(Weight Graph)에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적
최단 경로 문제 종류
1.
단일 출발 및 단일 도착 최단 경로 문제
•
그래프 내의 특정 노드 u에서 출발, 또 다른 톡정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제
2. 단일 출발 최단 경로 문제
•
그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제
3. 전체 쌍 최단 경로
•
그래프 내의 모든 노드 쌍 (u,v)에 대한 최단 경로를 찾는 문제
최단 경로 알고리즘 - 다익스트라 알고리즘
•
다익스트라 알고리즘은 위의 최단 경로 문제 종류 중, 2번에 해당
•
하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 문제
