求最短路徑中BELLMANFORD算法實(shí)現(xiàn)的C程序？Dijkstra算法不能判斷具有負(fù)權(quán)邊的圖的最短路徑。如果遇到負(fù)權(quán)值，當(dāng)沒有負(fù)權(quán)值循環(huán)時(shí)（負(fù)權(quán)值循環(huán)意味著循環(huán)的權(quán)值之和為負(fù)），即使有負(fù)權(quán)值邊，be

求最短路徑中BELLMANFORD算法實(shí)現(xiàn)的C程序？

Dijkstra算法不能判斷具有負(fù)權(quán)邊的圖的最短路徑。如果遇到負(fù)權(quán)值，當(dāng)沒有負(fù)權(quán)值循環(huán)時(shí)（負(fù)權(quán)值循環(huán)意味著循環(huán)的權(quán)值之和為負(fù)），即使有負(fù)權(quán)值邊，bellman-Ford算法也能正確地找到最短路徑，。

Bellman-Ford算法可以解決更一般情況下的單源最短路徑問題（具有負(fù)權(quán)重邊）。對(duì)于給定的加權(quán)（有向或無向）圖G=（V，e），其源點(diǎn)是s，加權(quán)函數(shù)w是邊集e的映射，對(duì)圖G運(yùn)行Bellman-Ford算法的結(jié)果是一個(gè)布爾值，它表示圖中是否存在從源點(diǎn)s可到達(dá)的負(fù)權(quán)環(huán)。如果不存在這樣的循環(huán)，算法將給出從源點(diǎn)s到圖G的任意頂點(diǎn)v的最短路徑d[v]。