doongu doongu

우리는 보통 다익스트라를 배우고 난 뒤에 "음수 간선" 간선에서 동작하는 Bellman Ford 알고리즘을 공부합니다. 하지만 "음수 간선"이라는 조건만으로 다익스트라가 작동하지 못할까요? 아닙니다. 아래 그래프는 다익스트라가 동작함을 알 수 있어요. graph = { 'A': {'B': -100, 'C': 10}, 'B': {'C': 10} #'A': {'B': -100}, #'B': {'C': 10}, #'C': {'A':10} } import heapq def dijkstra(graph, start): distances = {node: 1e9 for node in graph} # start로 부터 '다른 node'의 거리 값을 저장하기 위함 distances[start] = 0 # start에서 s..