다익스트라 알고리즘

다익스트라 알고리즘은 특정한 노드에서 출발하여 다른 모든 정점까지의 최단 경로를 찾는 데 사용되는 알고리즘이다.

BFS의 경우 간선의 가중치가 존재할 경우 사용할 수 없기 때문에 이 경우 다익스트라를 사용할 수 있다.

출발점으로 지정된 노드에서 직접적으로 연결되어 있지 않더라도, 다른 노드를 경유하여 갈 수 있는 경로가 존재한다면 경유하는 다른 노드를 거쳐 목표 노드로 가는 비용을 계산하여 출발 노드에서 해당 노드까지의 경로가 존재하는 식으로 취급한다.

가령 해당 그래프를 예시로 들 경우 1번 노드와 4번 노드는 직접적으로 연결되어 있지 않지만 2번 노드를 경유하여 4번 노드로 가는 경로가 존재하기 때문에 1 -> 4 번노드로의 최단 거리는 1->2 , 2->4의 경로의 비용의 합인 5 + 6인 11로 취급할 수 있다.

알고리즘의 동작 방식을 순서대로 정리하자면,

1. 출발점의 거리를 0으로 설정, 그리고 직접적으로 연결된 정점과의 거리와 가중치를 설정하고 연결되어 있지 않은 정점과의 거리는 무한에 가까운 아주 높은 값으로 설정한다.

(비교 과정에서 해당 정점으로 접근할 수 있는 더 짧은 거리가 존재할 경우 정점과의 거리를 더 짧은 것으로 갱신할 것이기 때문에 모든 정점을 순회했음에도 해당 정점과의 거리가 무한이라면 시작점과 해당 정점은 다른 노드를 경유하더라도 접근할 수 없다는걸 알 수 있다.)

2. 우선순위 큐를 활용하여 출발점을 시작으로 이동할 때마다 해당 정점과 연결된 간선들을 조사하여 해당 간선을 통해 다른 정점에 도달하는 데에 드는 비용을 계산한다. 또 이전에 계산된 최단 거리보다 더 짧은 경로를 찾으면 해당 정점의 거리를 갱신하고, 우선순위 큐에 추가한다.

3. 우선 순위 큐에서 가장 짧은 거리를 가진 정점을 선택하고, 해당 정점과 연결된 간선을 통해 다른 정점까지의 최단 거리를 갱신한다. 이 과정을 모든 정점을 방문할 때까지 반복한다.

(우선순위 큐를 사용하지 않더라도 목표 노드까지의 가중치와 경유 노드까지의 가중치 + 경유 노드로부터 목표 노드까지의 가중치를 비교해서 각 노드까지의 거리를 배열에 담는 식으로도 사용할 수 있다.)