|Dijkstra 알고리즘|

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