그래프의 최단거리 구하는 알고리즘

[gyurim]

그래프의 최단거리 구하는 알고리즘

다익스트라 알고리즘

• 하나의 정점에서 출발했을 때, 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
• 다이나믹 프로그래밍 문제임 -> 최단 거리는 여러개의 최단 거리로 이루어져있기 때문
• 현재까지 알고 있던 최단 경로를 계속해서 갱신
• 선형 탐색으로 구현 시, 시간복잡도 = 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. 전체 배열이 성공적으로 갱신