[알고리즘] 벨만-포드 알고리즘 vs 존슨 알고리즘

그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 방법은 여러 가지가 있습니다. 그 중에서도 벨만포드 알고리즘과 존슨 알고리즘은 음의 간선이 포함된 그래프에서 최단 경로를 찾는 데 효과적인 두 가지 알고리즘입니다. 벨만-포드 알고리즘 벨만포드 알고리즘은 그래프의 모든 간선을 반복적으로 순회하면서, 해당 간선을 거쳐가는 경로의 거리가 현재까지 알려진 최단 거리보다 짧다면 최단 거리를 갱신하는 방식으로 최단 경로를 구합니다. def bellman_ford(graph, start): """ 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 Args: graph: 그래프 start: 출발 정점 Returns: 각 정점까지의 최단 경로 """ dist = [float("inf..