다익스트라 알고리즘

다익스트라 알고리즘은 방향 그래프에서 최단 거리를 구하는 알고리즘이다.(음수의 가중치는 허용하지 않는다.)

보통 시작점에서 다른 점들 간의 거리를 구할 때 사용된다.(시작점에 대해서만 알 수 있음.)

만약 노드가 1, 2, 3, 4, 5가 있고 1에서 시작을 하면 2, 3, 4 ,5까지의 최단거리를 구할 수 있다는 의미이다.(2에서 4까지의 최단거리나 2에서 5까지의 최단거리를 구할 수 없음.)

만약 모든 노드에 대해 최단거리를 알고 싶다면 플로이드-워셜 알고리즘을 사용하면 된다.(단 이 알고리즘은 시작복잡도가 O(N^3)이기 때문에 입력값이 크면 사용하지 못한다.

 

다익스트라 알고리즘에서는 우선순위 큐라는 자료구조를 사용한다.

지금까지 계산된 거리 중 가장 가까운 거리에 대해 탐색하기 위해 우선순위 큐를 사용한다.

그리고 거리의 대한 값을 저장하기 위해 배열을 선언해줘야 한다.(배열은 처음에 INF로 초기화한다.)

 

가장 가까운 거리에 노드를 선택하고 이 노드와 인접한 노드에 대해 검사를 한다.(검사를 하는 거지 방문하는 것은 아님)

만약 저장된 거리의 값보다 작다면 갱신한다.

이미 방문된 노드는 그 보다 작은 값이 나올 수 없으므로 visited배열을 이용해서 방문여부를 확인해 준다.

만약 visited배열을 사용해서 방문여부를 확인하지 않으면 시간복잡도가 증가한다.

(visited배열을 사용하지 않고 if (dist[cur] < cost) continue; 를 사용할 수도 있음. 이미 최적화 된 경우에는 continue)

 

예를 들어 2로가는 경로가 3, 4, 5, 6 이 있다고 치자 3, 4, 5, 6이 연속해서 갱신할 가능성도 존재한다.

6에서 2로 들어가는 경로를 방문하면 이전에 갱신한 3, 4, 5의 데이터는 필요가 없어진다.

그러므로 이미 방문된 노드는 다시 방문하지 않는다.

 

이처럼 다익스트라 알고리즘은 정해진 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘이다.

직접 여러 번 구현해 보아야 감이 잡힌다.