[최단거리] 벨만-포드 알고리즘 (Bellman-Ford)
벨만-포드 알고리즘이란? 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 이때, 다익스트라와 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있다. 음의 사이클이 없고 한 노드에서 다른 노드까지의 최단 경로를 많아봐야 V-1개의 간선을 지난다는 가정에서 시작된다. 다익스트라 알고리즘에 비해 효율이 떨어지지만 더 많은 그래프에 대해서 정확한 답을 구할 수 있다. 다익스트라벨만-포드음수 가중치XO음수 사이클XX시간복잡도O(mlog n)O(mn)❗️벨만-포드가 가중치가 음수인 경우에도 최단 거리를 구할 수 있는 이유다익스트라 알고리즘에서는 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해서 1단계씩 최단 ..
