포드-벨만 알고리즘
n 꼭지점과 m 가장자리, 일부 시작 꼭지점 vG가 주어집니다. > . 정점 v에서 다른 모든 정점까지의 최단 경로 길이를 찾는 데 필요합니다.
Dijkstra와 마찬가지로 Ford-Bellman은 꼭지점 1에서 다른 모든 정점까지의 거리를 찾지만 음의 가장자리로 작동.
<사업부>
Ford-Bellman 알고리즘 자체는 여러 단계(
n-1)로 구성됩니다. 각 단계에서 그래프의 모든 가장자리가 검사되고 알고리즘은 비용
c의 각 가장자리
(a, b)를 따라 완화하려고 시도합니다.
가장자리를 따라 이완 — 이것은
d[a] 의 의미를 개선하려는 시도입니다. 값
d[b] + c. 사실 이것은 우리가 edge 상단에 대한 현재 답변입니다.
d 배열은 Dijkstra와 마찬가지로 시작 정점에서 가장 짧은 길이의 배열입니다. 처음에는 시작 정점을 제외하고 가능한 한 큰 숫자로 채웁니다. 0.
에지를 저장하기 위해 인접 행렬이나 가중치 행렬이 아니라 에지가 어느 노드에서 출발하는지(
from), 어느 노드로 오는지(
to) 및 무게(비용).
구조체 가장자리 {
int from, to, 비용;
};
벡터<에지> 가장자리;
INF 상수는 숫자 "무한대"를 나타냅니다. - 가능한 모든 경로 길이를 분명히 초과하는 방식으로 선택해야 합니다.
<사업부>
알고리즘의 가장 간단한 구현:
d[v] = 0;
for (int i=0; i