가중치가 음수인 경우에 최단거리를 구하는 벨만 포드 알고리즘 익히기

1. 가중치에 음수가 포함된 경우 모든 간선의 비용이 양수일때는 다익스트라 알고리즘을 사용하면 특정 노드에서 다른 노드까지 최단 거리로 가는 비용을 효과적으로 구해준다 다음에서 1번 노드에서 다른 노드까지 가는 최단 비용은 얼마일까? 다익스트라 알고리즘을 이용해서 구하면 최단거리를 간단히 구할 수 있다 import heapq INF = 10000000000000000000000 dist = [INF]*7 graph = [[],[(2,6),(3,2)],[(3,2),(4,2)],[(5,1)],[(6,2)],[(2,1),(4,3),(6,4)],[]] q = [] heapq.heappush(q,(0,1)) dist[1] = 0 while q: d,u = heapq.heappop(q) if dist[u] < d:..