다익스트라 알고리즘(Dijkstra Algorithm)

1. 개념

 다익스트라 알고리즘은 어떤 노드에서 다른 노드까지의 거리(가중치)가 주어졌을 때

특정 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다.

이때 음의 가중치가 존재해서는 안되고, 방향-무방향 그래프 모두 가능하다.

2. 구현

Distance[i] : 출발점(S)에서 i 정점까지의 최단거리를 저장하는 배열

--> 초기화 과정에서 Distance[S] = 0 을 제외한 나머지는 모두 무한대로 초기화한다.

방문하지 않은 정점 중에서 Distance가 최소인 정점 I를 선택한다.

정점 I와 인접한 모든 정점 J에 대해서 현재까지 저장된 최단거리보다 새로운 정점을 거쳐서 가는 거리가

더 작을 경우에는 D[j] = D[i] + 새로운 정점까지의 거리로 갱신한다.

말로만 설명해서는 알기 힘들고 이 개념은 예제 코드를 참고하기를 바란다. (우선순위 큐를 사용했다)

[다익스트라 알고리즘 예제 : http://gyutts.tistory.com/115?category=755806]