# 그래프의 최단거리 구하는 알고리즘 ## 다익스트라 알고리즘 - **하나의 정점에서 출발했을 때, 다른 모든 정점으로의 최단 경로를 구하는 알고리즘** - 다이나믹 프로그래밍 문제임 -> 최단 거리는 여러개의 최단 거리로 이루어져있기 때문 - **현재까지 알고 있던 최단 경로를 계속해서 갱신** - 선형 탐색으로 구현 시, 시간복잡도 = O(N^2) - 힙으로 구현 시, 시간복잡도 = O(NlogN) ### 과정 - 1 -> 3 으로 가는데 6의 가중치 존재, 1 -> 2로 가는데 3의 가중치가 존재 - 이때, 1 -> 3 경로의 최단 경로의 가중치는 <6> - 2 -> 3 으로 가는데 1의 가중치가 존재 - 이때, 1 -> 3 경로는 1 -> 2 -> 3 경로가 가장 최단 경로임을 알 수 있고 가중치는 <4> - 따라서 1 -> 3 최단 경로를 갱신해준다. ### 작동 과정 1. 출발 노드를 설정한다. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다. 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. 4. 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다. 5. 위 과정에서 3번 ~ 4번을 반복한다. - 방문한 노드 != 인접 노드 ## 플로이드 알고리즘 - **모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘** - 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면, 플로이드 와샬 알고리즘은 기본적으로 **거쳐가는 정점**을 기준으로 알고리즘을 수행 - 소스코드가 간결 - 시간복잡도 = O(N^3) ### 작동 과정 1. 노드 1을 거쳐가는 경우 - X에서 Y로 가는 최소 비용 VS X에서 노드 1로 가는 비용 + 노드 1에서 Y로 가는 비용 - 즉, 1을 거쳐서 가는 경우가 더 빠른 경우가 존재한다면 빠른 경우로 최소 비용을 계산 2. 노드 2를 거쳐가는 경우 3. 위와 같은 방식으로 노드 3과 노드 4에 대해서도 수행해주면 됨 4. 전체 배열이 성공적으로 갱신
