求任意权值最短路径的Bellman-Ford算法实现

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

补充：软件开发 , C++ ,

上一个：count number更正
下一个：零零散散学算法之浅析内存管理的方式