Bellman-Ford算法可以用來解決所要求的最短路徑的圖中含有負數邊的情形。 算法的基本思想：如果兩個結點間存在最短路徑，那麼這條路徑中各個結點最多經過一次(因為如果超過一次，說明路徑中有環，如果是正數環，會使路徑權值增長；若為負數環，最短路徑不存在；若為零環，不影響結果)。因此我們只需迭代n-1次，將起始點到其他各點最多經過n-1條邊的最短路徑求出來即可。 [cpp] #include <iostream> using namespace std; const int MaxSize=10; int arr[MaxSize][MaxSize]; www.2cto.com int dist[MaxSize]; //保存起點到各結點最短路徑的數組 int path[MaxSize]; //數組元素保存最短路徑中經過的前一個結點 int numNode=0; void createArr() { cin>>numNode; for(int i=0;i<numNode;++i) for(int j=0;j<numNode;++j) cin>>arr[i][j]; } //計算任意權值的最短路徑的Bellman-Ford算法 //從頂點v找到所有其他定點的最短路徑 void BellmanFord(const int v) { //dist數組和path數組的初始化 for(int i=0;i<numNode;++i) { dist[i]=arr[v][i]; if(i!=v) path[i]=v; else path[i]=-1; } //最多迭代n-1次 for(int len=2;len<numNode;++len) for(int u=0;u<numNode;++u) if(u!=v) { //每次都以u為終點，看以i為中轉點到達u的總權值是否比dist[u]小， //小的話改寫dist[u] for(int i=0;i<numNode;++i) if(dist[u]>dist[i]+arr[i][u]) { dist[u]=dist[i]+arr[i][u]; path[u]=i; } } //輸出起始結點到各結點的最短路徑 for(int i=0;i<numNode;++i) cout<<dist[i]<<" "; cout<<endl; //輸出最後一個結點最短路徑經過的各結點(其他結點可用類似做法) int end=numNode-1; while(path[end]!=-1) { cout<<path[end]<<" "; end=path[end]; } cout<<endl; } int main() { createArr(); BellmanFord(0); }
