🖥 최단 경로 알고리즘

🧭 플로이드 와샬

용도 : 각 정점간 최단경로를 구할 때

• 공간 복잡도 : v^2
• 시간 복잡도 " v^3

장단점

• 소스가 더 간결함
• 간선 수가 많으면 다익스트라 알고리즘보다 빠를 수 있음
• 시작점으로부터 각 정점까지 최단거리만 구할때에 보통 다익스트라가 압도적으로 빠름
• 그래프에 음의 가중치 간선이 있으면 다익스트라 알고리즘은 사용불가 But 플로이드 알고리즘은 사용 가능함

🧭 다익스트라

용도 : 시작점으로 부터 나머지 정점까지 최단거리를 구할시에 사용

• 공간 복잡도 : v^2 , V+E(인접리스트)
• 시간 복잡도 " v^2(인접행렬) 우선순위큐 VlogV

🖥 사용시기

• 정점간 최단경로를 모두 구해야함
  간선이 매우 많으면 플로이드 알고리즘
  간선이 작을시 다익스트라
• 시작점으로부터 나머지 정점만 최단거리를 구할때에는
  다익스트라를 사용
• 시간에 영향을 안받을경우 플로이드를 사용함
• 음의 가중치가 존재하면 플로이드와샬을 사용함

🧭 다익스트라 예제

최단경로 백준

import sys
import heapq

input = sys.stdin.readline
INF = 1e9


def dijkstra(start):
    heap = []
    heapq.heappush(heap, (0, start))  # 가중치 , 간선
    distance[start] = 0
    while heap:
        cost, index = heapq.heappop(heap)
        if distance[index] < cost:
            continue
        # 목적지까지 거리가 현재 인덱스의 cost보다 작을 경우에는
        # 굳이 다음걸 확인할 필요가 없다.
        for next, c in arr[index]:
            if distance[next] > cost + c:
            # 목적지 next인덱스의 가중치보다 현재 인덱스의 가중치 + (현재인덱스에서 목적지 간선의 가중치)가
            # 더 작을경우에 가중치를 업데이트 시켜준다
                distance[next] = cost + c
                # 가중치 업데이트
                heapq.heappush(heap, [cost + c, next])


n, m = map(int, input().split())
start = int(input())
arr = [[] for i in range(n + 1)]
distance = [INF for i in range(n + 1)]
for i in range(m):
    u, v, w = map(int, input().split())
    # u에서 v로 가는 가중치는 w이다.
    arr[u].append([v, w])
dijkstra(start)
for i in range(1, n + 1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])