介紹

與Dijkstra算法不同，Bellman-ford能對(duì)付有負(fù)權(quán)重的邊，而且可以檢測(cè)negative cycle.
假設(shè)V存的是所有的頂點(diǎn)（vertex），E存的是所有的邊（edge），w(u, v)代表頂點(diǎn)u到頂點(diǎn)v的權(quán)重，PI[v]存的是從哪一個(gè)頂點(diǎn)到頂點(diǎn)v（PI[A]=s表示s->A）
以這幅圖為例子。

偽代碼

初始化

偽代碼

for v in V:d[v]=INFINITYPI[v]='' d[s]=0

循環(huán)

for i in range(1, len(V)): # 從i到len(V)-1for w(u,v) in E:# relax操作if d[v] > d[u] + w(u,v):d[v] = d[u] + w(u,v)PI[v] = u

檢查有沒有negative-weight cycle

什么是negative-weight cycle？

那種每次循環(huán)一遍d[v]都會(huì)減少的，循環(huán)無數(shù)次后，d[v]會(huì)趨近于負(fù)無窮。

for w(u,v) in E:if d[v] > d[u] + w(u,v):return negative_cycle_error

總結(jié)

以上是生活随笔為你收集整理的Bellman-ford算法图解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。