다익스트라 알고리즘

다익스트라 알고리즘은 다음과 같이 흘러간다.

 

사전 조건:

1부터 N까지의 노드, 시작 노드는 1로 한다.

간선 정보는 w[i][j] (i에서 j로 가는 간선의 가중치, 비용).

dist[i]는 시작 노드에서 i까지의 거리 (dist[1] = 0)

 

1) dist[]를 초기화한다. dist[1] = 0, 나머지 dist[i] =  INF, (INF는 매우 큰 수, i != 0)

 

2) 1부터 N까지 노드 중 dist[i]가 최소인 노드를 선택한다. 처음에는 당연히 시작 노드인 1번 노드가 선택된다. (한 번 선택한 후에 다시 보지는 않는다. (= 방문과 같다))

 

3) 인접 노드(j)를 방문하는데, 다음 조건을 만족하는 경우 dist[j]를 갱신해준다.

조건 : if (dist[j] > dist[i] + w[i][j]) dist[j] = dist[i] + w[i][j]   

 

4) 이런 식으로 모든 노드가 갱신될 때 끝난다.

 

주의 사항:

• 다익스트라 알고리즘은 간선의 가중치가 0이거나 양수일 경우에만 사용할 수 있다. 

 

Tip:

• C++에서 priority_queue를 이용하면 2)의 최소 노드 선택을 nlog(n)으로 시간복잡도를 줄일 수 있다.

 

참고:

https://wondy1128.tistory.com/95

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

https://hsp1116.tistory.com/42

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