求任意权值最短路径的Bellman-Ford算法实现
Bellman-Ford算法可以用来解决所要求的最短路径的图中含有负数边的情形。 算法的基本思想：如果两个结点间存在最短路径，那么这条路径中各个结点最多经过一次(因为如果超过一次，说明路径中有环，如果是正数环，会使路径权值增长；若为负数环，最短路径不存在；若为零环，不影响结果)。因此我们只需迭代n-1次，将起始点到其他各点最多经过n-1条边的最短路径求出来即可。
代码：#include <iostream> using namespace std; const int MaxSize=10; int arr[MaxSize][MaxSize]; 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); } 站长网
