- 한 정점에서 다른 정점으로
가는 최단 경로를 구하기
위해서는 그 정점에서 다른
모든 정점으로 가는 최단경로를
구해야 한다.
- 가중치가 없는 그래프의
최단경로 : 나비 우선 탐색
- 가중치가 있는 그래프의
최단경로 : Dijkstra의 알고리즘
- 출발점에서 시작하여
현재의 leaf 노드까지의
값과 leaf 노드에 인접한
노드의 값의 합이 가장
작은 노드를 다음 노드로
선택하고 그 경로를 최단
경로(트리형태)에 포함시킨다.
이 과정을 모든 노드가
선택될 때까지 반복한다.
|
|