[알고리즘/C++] 다익스트라 알고리즘(Dijkstra's Algorithm)

다익스트라 알고리즘은 벨만 포드 알고리즘과 같이 특정 노드로부터 다른 노드들까지의 최단 거리를 계산하는 알고리즘으로, 벨만 포드보다 더 효율적이로 대중적으로 쓰이는 알고리즘이다. 다익스트라의 기본 메커니즘은 다음과 같다. 위 그래프에서 노드 1을 기준으로 각 노드까지의 최단 거리를 찾는다고 할 때, 노드 1에서 가장 가까운 노드는 거리 2를 가진 노드 2이다. 초점은 노드 2로 옮겨간다. 노드 2까지의 거리는 2이다. 노드 2를 방문했으니 나머지 노드들 중에 1과 가장 가까운 노드는 노드 3이다. 노드3까지의 거리는 3으로 갱신된다. 우선순위 큐에 노드 3에 대한 갱신 정보를 넣어준다. 노드 3의 이웃 노드들까지 시야를 확대해서 나머지 노드들 중 가장 가까운 노드를 찾는다. 노드 4는 노드 3을 경유함으..

2023.08.03