[자료구조] Dijkstra's algorithm

Dijkstra's algorithm: 방향그래프(directed graph)에서 한 노드에서 다른 노드까지 최소 비용을 갖는 길 찾기

performance of Dijkstra's algorithm: O(N^2)

 

 

아래 그래프에서 Dijkstra's algorithm을 이용하여 노드A에서 노드E까지 최소 비용을 갖는 길 찾기

 

 

1. 노드A에서 시작해서 가장 비용이 적은 노드를 선택한다.

2. 1번에서 선택한 노드를 거쳐서 더 비용이 적다면 그 비용을 다시 적는다.