[자료구조] Dijkstra 최단 경로 알고리즘

Dijkstra 최단 경로 알고리즘

다익스트라(Dijkstra) 알고리즘은 주어진 그래프에서 한 출발점으로부터 다른 모든 노드까지의 최단 경로를 구하는 알고리즘입니다. 다익스트라 알고리즘은 가중치가 있는 그래프에서 사용되며, 주로 길 찾기 문제 등에 활용됩니다.

다익스트라 알고리즘의 동작 방식은 다음과 같습니다:

출발점을 설정하고 출발점으로부터의 거리를 저장하는 배열을 초기화합니다. 출발점의 거리는 0으로 설정하고, 다른 모든 노드의 거리는 무한대로 초기화합니다.

방문하지 않은 노드 중에서 출발점으로부터의 거리가 가장 짧은 노드를 선택합니다. 이를 현재 노드로 설정합니다.

현재 노드와 연결된 모든 인접한 노드들을 순회하면서, 출발점으로부터의 거리를 업데이트합니다. 만약 현재 노드를 통해 인접한 노드로 가는 거리가 기존의 거리보다 더 짧다면, 해당 노드의 거리를 업데이트합니다.

모든 노드를 방문할 때까지 2번과 3번의 과정을 반복합니다.

최종적으로 모든 노드로부터의 최단 거리가 결정되고, 이를 결과로 반환합니다.

다익스트라 알고리즘은 탐욕적인 방법을 사용하여 노드를 선택하고, 최단 거리를 업데이트하는 과정을 반복합니다. 이 과정은 모든 노드를 방문할 때까지 반복되므로, 최악의 경우 그래프의 모든 노드와 간선을 순회하게 됩니다.

다익스트라 알고리즘은 최소 힙(우선순위 큐)을 사용하여 효율적으로 구현할 수 있습니다. 최소 힙을 활용하면 노드 선택과 거리 업데이트 과정에서 가장 작은 거리를 가진 노드를 빠르게 찾을 수 있습니다.

다익스트라 알고리즘의 시간 복잡도는 일반적으로 O((V + E)logV)입니다. 여기서 V는 노드의 수, E는 간선의 수를 의미합니다.

플로이드 최단 경로 알고리즘은 그래프에서 모든 노드 쌍 간의 최단 경로를 찾는 알고리즘입니다. 플로이드 알고리즘은 다이나믹 프로그래밍 기법을 사용하여 각 노드를 중간 경유지로 가정하고, 모든 노드 쌍 간의 최단 경로를 구하는 방식으로 작동합니다.

플로이드 알고리즘의 동작 방식은 다음과 같습니다:

초기 그래프 설정: 그래프의 인접 행렬을 생성하고, 각 간선의 가중치를 초기화합니다. 만약 노드 간에 직접적인 간선이 없는 경우, 해당 가중치를 무한대로 설정합니다.
중간 경유지 반복: 모든 노드를 중간 경유지로 가정하며, 각 노드 쌍 간의 최단 경로를 업데이트합니다. 중간 경유지를 하나씩 추가할 때마다 모든 노드 쌍에 대해 최단 경로를 계산하여 갱신합니다.
최단 경로 계산: 중간 경유지를 추가할 때마다 인접 행렬을 업데이트하여 각 노드 쌍 간의 최단 경로를 계산합니다. 각 노드 쌍에 대해 현재 경로와 새로운 경로를 비교하여 더 짧은 경로로 업데이트합니다.
최단 경로 출력: 최종적으로 모든 노드 쌍 간의 최단 경로가 계산되면, 이를 출력하거나 필요에 따라 활용합니다.

플로이드 알고리즘은 음의 가중치를 가지는 그래프에서도 동작할 수 있고, 그래프의 크기에 상관없이 모든 노드 쌍 간의 최단 경로를 찾을 수 있습니다. 하지만 시간 복잡도는 O(n^3)으로 큰 그래프에서는 계산 비용이 증가할 수 있습니다.

플로이드 최단 경로 알고리즘은 도로 네트워크, 통신 네트워크, 라우팅 테이블 등 다양한 분야에서 사용됩니다. 예를 들어, 인터넷의 라우터 간 최단 경로 결정, 도시 간의 교통 흐름 분석, 항공 노선 최적화 등에 활용됩니다.