[Java] 다익스트라 알고리즘

음의 가중치가 없는 그래프의

한 노드에서 각 모든 노드까지의 최단 거리를 구하는 알고리즘

 

[시간복잡도]

O((V+E)logV)이지만

열결 그래프라면 O(ElogV)까지 줄일 수 있다.

일반적으로는 우선순위 큐를 이용하는 것이 낫다고 한다.

 

[매커니즘]

1 ) 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택

2 ) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신

 

[초기화]

A노드에서 A노드로 가는 가는 지점이 가장 짧다.라고 정의

 

[알고리즘 적용]

방문하지 않은 노드 중 가장 비용이 적은 노드를 선택하며 값 갱