벨만-포드와 음의 간선

다익스트라는 꺼낸 거리가 최종값이라고 가정하지만, 음수 간선 때문에 나중에 경로 비용이 더 작아질 수 있습니다. 그래서 제대로 작동하지 않습니다.

벨만-포드는 음수 간선 가중치를 처리할 수 있습니다. 다익스트라보다 느리지만 그리디 논리를 신뢰할 수 없는 경우에도 안정적으로 작동합니다.

모든 간선을 반복해서 완화합니다. dist[u]에 간선 가중치를 더한 값이 dist[v]보다 작으면 dist[v]를 그 작은 값으로 갱신합니다.

최단 경로에는 간선이 최대 V-1개만 포함되므로, 모든 간선을 V-1회 반복해서 완화하면 모든 거리를 확정할 수 있습니다.

다익스트라와 마찬가지로 시작점의 거리는 0으로, 나머지 모든 거리는 무한대로 설정하고 시작합니다.

각 순회에서는 전체 간선 목록을 한 번 훑으며 모든 간선을 완화합니다. 개선된 값은 매 순회마다 한 단계씩 바깥으로 퍼져 나갑니다.

k회 순회한 뒤에는 간선을 k개 사용하는 모든 최단 경로가 올바르게 계산됩니다. V-1회 순회하면 모든 단순 최단 경로가 완성됩니다.

한 번 더 순회합니다. 이때도 거리가 줄어든다면 비용이 계속 작아지고 있다는 뜻이며, 음수 사이클이 있음을 나타냅니다.

음수 사이클이 있으면 유한한 최단 경로가 존재하지 않습니다. 비용을 제한 없이 낮추면서 사이클을 계속 돌 수 있기 때문입니다.

V번의 순회에 걸쳐 E개의 간선을 완화하므로 벨만-포드의 시간 복잡도는 O(V * E)입니다. 작거나 중간 크기의 그래프에 적합합니다.

음수가 아닌 가중치와 속도가 중요하면 다익스트라를 선택합니다. 음수 가중치가 있거나 문제가 되는 사이클을 찾아야 하면 벨만-포드를 선택합니다.

V-1회 순회한 뒤 한 번 더 순회했는데도 거리가 줄어듭니다. 이것은 무엇을 의미하나요?

모든 간선을 V-1회 반복해서 완화한 다음, 음수 사이클을 찾기 위해 한 번 더 수행합니다. O(V*E) 시간이 걸리지만 다익스트라를 사용할 수 없는 경우에도 작동합니다. ✅