벨만-포드 알고리즘 편집하기 (부분)

== 예시==
다음은 음의 가중치 간선을 포함하는 예제 그래프와 벨만-포드 알고리즘 수행 과정을 나타낸 것이다.

그래프 구조:

[[파일:음의 간선이 있는 그래프.png|700x700픽셀]]

간선 목록: 아래 순서대로 순회한다. 벨만-포드는 순서에 따라 알고리즘의 중간 전개가 달라질 수 있다. 

* A → B (6)

*A → C (7)
*B → C (8)
*B → D (5)
*B → E (-4)
*C → D (-3)
*C → E (9)
*D → B (-2)
*E → D (7)
시작 정점: A

거리 테이블 (d[i]는 정점 i까지의 최단 거리):

{| class="wikitable"
!반복 단계||A||B||C||D||E
|-
|초기값||0||∞||∞||∞||∞
|-
|1회 반복
|0||2|| 7||4||2
|-
|2회 반복 ||0 ||2||7||4|| −2
|-
|3회 반복 || 0 || 2||7|| 4||−2
|-
|4회 반복 ||0 ||2||7||4||−2
|}
'''1회 반복 – 간선별 처리'''

# A → B (6): A = 0이므로 B = 0 + 6 = 6 → B 갱신
# A → C (7): A = 0이므로 C = 0 + 7 = 7 → C 갱신
# B → C (8): B = 6이므로 C = 6 + 8 = 14 → 기존 C = 7이므로 변화 없음
# B → D (5): B = 6이므로 D = 6 + 5 = 11 → D 갱신
# B → E (−4): B = 6이므로 E = 6 − 4 = 2 → E 갱신
# C → D (−3): C = 7이므로 D = 7 − 3 = 4 → D 갱신 (기존 11 → 4)
# C → E (9): C = 7이므로 E = 7 + 9 = 16 → 기존 E = 2이므로 변화 없음
# D → B (−2): D = 4이므로 B = 4 − 2 = 2 → B 갱신 (기존 6 → 2)
# E → D (7): E = 2이므로 D = 2 + 7 = 9 → 기존 D = 4이므로 변화 없음
'''2회 반복 – 간선별 처리'''
# A → B (6): A = 0이므로 B = 0 + 6 = 6 → 기존 B = 2이므로 변화 없음
# A → C (7): A = 0이므로 C = 0 + 7 = 7 → 기존 C = 7이므로 변화 없음
# B → C (8): B = 2이므로 C = 2 + 8 = 10 → 기존 C = 7이므로 변화 없음
# B → D (5): B = 2이므로 D = 2 + 5 = 7 → 기존 D = 4이므로 변화 없음
# B → E (−4): B = 2이므로 E = 2 − 4 = −2 → E 갱신 (기존 2 → −2)
# C → D (−3): C = 7이므로 D = 7 − 3 = 4 → 기존 D = 4이므로 변화 없음
# C → E (9): C = 7이므로 E = 7 + 9 = 16 → 기존 E = −2이므로 변화 없음
# D → B (−2): D = 4이므로 B = 4 − 2 = 2 → 기존 B = 2이므로 변화 없음
# E → D (7): E = −2이므로 D = −2 + 7 = 5 → 기존 D = 4이므로 변화 없음

'''3회 반복 & 4회 반복'''
*모든 간선 검사 시 더 이상 갱신 없음 (거리 안정화됨)
*정점이 5개이므로 5 - 1 = 4회 까지만 반복된다.