https://velog.io/@yoopark/shortest-path

위 글이 너무 길어서 구현 부분을 따로 보면서 외우기가 힘드니까 구현부만 발췌한 글을 새로 작성한다.

알고리즘에 대한 설명은 따로 하지 않겠다. 자세한 내용은 위 글에 다 나와있다.

0. graph 입력 양식

다익스트라, 벨만-포드 전반부(defaultdict(list))

import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import defaultdict
import heapq # dijkstra에서만
INF = int(1e9)

# V = Vertex(정점), E = Edge(간선)
V, E = map(int, input().split())
start = int(input())
graph = defaultdict(list)
for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append((b, c))

dist = [INF] * (V+1) # dist[0]은 안 씀

플로이드-워셜 전반부(2D array)

import sys
input = lambda: sys.stdin.readline().rstrip()
INF = int(1e9)

graph = [[INF] * (V+1) for _ in range(V+1)]

for i in range(1, V+1):
	graph[i][i] = 0

for _ in range(E):
    a, b, c = map(int, input().split())
    graph[a][b] = c

1. 다익스트라

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dist[start] = 0
    while q:
        weight, node = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if dist[node] < weight:
            continue
        for adj_node, adj_weight in graph[node]:
            cost = weight + adj_weight
            if cost < dist[adj_node]:
                dist[adj_node] = cost
                heapq.heappush(q, (cost, adj_node))

dijkstra(start)
print(dist[1:])

2. 벨만-포드

def bellman_ford(start):
    dist[start] = 0
    for cnt in range(1, V+1):
        for i in range(1, V+1):
            if dist[i] == INF:
                continue
            for node, weight in graph[i]:
                if dist[i]+weight < dist[node]:
                    if cnt == V:
                        return True
                    dist[node] = dist[i]+weight
    return False
            
have_minus_cycle = bellman_ford(start)
if have_minus_cycle:
    print('음수 사이클이 있습니다.')
else:
    print(dist[1:])

3. 플로이드-워셜

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, V+1):
    for i in range(1, V+1):
        for j in range(1, V+1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(1, V+1):
	print(graph[i][1:])