[그래프 알고리즘]다익스트라 알고리즘

최단거리 알고리즘

다익스트라 알고리즘은 그래프의 한 노드에서 시작해 다른 노드들 까지의 최단 거리를 구하는 알고리즘 입니다.

노드들간의 엣지는 거리를 나타내는 가중치가 부여됩니다.

음의 가중치 엣지

다익스트라 알고리즘이 적용되는 그래프에는 가중치가 음수인 엣지가 있으면 안됩니다.

다익스트라 알고리즘은 노드들을 특정 순서로 방문하면서 시작노드에서 그 노드까지의 최단거리를 확정하는데,

음수 가중치 엣지가 존재한다면 한 노드까지의 최단거리를 확정할수 없습니다.

노드 방문 순서

일단 시작 노드부터 다른 노드들까지의 거리를 나타내는 표와 노드들의 방문 여부를 나타내는 표를 준비합니다.

시작노드에서 시작노드까지의 거리는 0으로 나머지는 매우 큰수로 초기화 합니다.

그리고 종료할 때까지 다음을 반복합니다.

1. 아직 방문하지 않았고 거리가 가장 작은 노드를 선택한다.
2. 선택한 노드를 방문 표시한다.
3. 선택한 노드와 연결된, 아직 방문하지 않은 노드들의 거리를 업데이트한다.

3번에서 노드들의 거리를 업데이트 할때는, (선택한 노드까지의 거리 + 엣지의 가중치)와 비교하여 작은 값으로 업데이트 합니다.

방문 표시가 된 노드들은 시작 점으로 부터의 최단 거리가 확정된 노드들입니다.

모든 노드들의 최단거리가 확정되면 종료합니다.

구현

우선순위 큐를 사용한 구현

기존의 구현은 다음 노드를 선택하기 위해 선택되지 않은 노드를 모두 확인해야 합니다.

노드의 개수가 많은 경우 다음 노드를 선택하기 위한 작업은 시간이 오래 걸릴 수 있습니다.

우선순위 큐를 사용하면 모든 노드를 확인하지 않고도 최단 거리 노드를 선택할 수 있습니다.

노드의 최단거리를 업데이트 한 후, 노드의 번호와 업데이트 된 최단 거리를 우선순위 큐에 넣으면,

우선 순위 큐의 가장 앞에 있는 원소는 최단 거리의 노드이므로 바로 선택하면 됩니다.