수학과의 좌충우돌 프로그래밍

Bellman-Ford 알고리즘이란? Bellman-Ford 알고리즘이란, 한 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘입니다. 벨만포드 알고리즘 외에 최단거리를 구하는 알고리즘은 여럿 있지만 벨만포드는 가중치가 음수 일 때도 사용이 가능합니다. 하지만 다익스트라 알고리즘에 비해 느리므로 가중치가 모두 양수일 경우에는 굳이 벨만포드 알고리즘을 사용할 필요가 없습니다. 음수간선 음수간선이 있을 경우 어떠한 문제가 생길지 알아보도록 하겠습니다. 아래 그래프에서 s 에서 출발하여 g 로 도착하는 경우를 생각해봅시다. s -> a -> b -> g 이 경우도 물론 음수간선이 존재합니다. 하지만 문제가 되는 경우는 없습니다. 3+(-4)+4 로 가중치 3으로 도착할 수 있습니다. s -> c -> d -..