[Algorithm] 최단경로 구하기 - Dijkstra 다익스트라 알고리즘, Floyd-Warshall 플로이드 워셜 알고리즘

다익스트라 Dijkstra

한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우

풀이 방법

1. 출발 노드를 설정한다
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중 최단거리가 짧은 노드 선택
4. 해당 노드 거쳐 다른 노드 가는 것중 최단거리 테이블 갱신

다익스트라 방법 1

구현하기 쉽지만 느리게 동작 O(V^2)

노드(V)	1(시작)	2	3	4
거리	0	INF	INF	INF

• 가장 가까웠던 노드(거리가 가장 낮은 노드) 방문하고, 그 노드에서 연결된 곳과 계산해서 갱신
• 한 단계당 하나의 노드에 대한 최단거리 확실하게 찾음
• O(V^2) = (전체 노드 한 번씩 방문해서) * (거리 한 번씩 확인)

[Tip] 입력값 많을 때 치환해서 쓰기

import sys
input = sys.stdin.readline

다익스트라 방법 2

구현하기 조금 더 까다롭지만 빠르게 동작 O(ElogV)

• Heap(Priority Queue) : 우선순위 가장 높은 데이터 추출
  heapq에 (거리,노드)저장
  

플로이드 워셜 Floyd-Warshall

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

다익스트라	플로이드 워셜
한 지점에 대한 최단 경로	모든 지점에 대한 최단 경로
단계별 해당 노드를 기준으로	단계별로 거쳐 가는 노드를 기준으로
1차원 리스트에 저장	2차원 리스트에 저장
그리디 알고리즘	다이나믹 프로그래밍

A-> B 비용이 3인데, A-> 1번 노드-> B의 비용이 2면 A-> B를 2로 갱신.
따라서, 현재 노드 제외 N-1개의 노드에서 (A,B)쌍을 선택하고 A-> 1번 노드-> B의 비용을 확인해 최단거리를 갱신한다

• 단계별로 (N-1)P(2) => N^2
• 따라서 O(N^3)

D(k) = min(A에서 B로 가는 최소 비용, A에서 K로 가는 비용+K에서 B로 가는 비용)

[Tip] 연결되지 않은 간선은 무한으로 넣어두기

INF = int(1e9)

References

이것이 코딩 테스트다 with 파이썬 - 나동빈 저