单源最短路径Bellman-Ford算法

对一个带权有向图G=(V,E），给定一个源顶点S，找出S到图中其他顶点v的最短路径即单源最短路径问题。该问题还有很多变体，像单终点最短路径、单对顶点最短路径、每对顶点间的最短路径等等。

最短路径问题是具有最优子结构的：一对顶点间的最短路径包含了该路径上的顶点间的最短路径。直观上理解，如果该路径上的两个顶点间的路径pij不是最短路径，那么用这两个顶点间的最短路径代替pij，那么就会出现一条更短的路径，与前面所说的最短路径矛盾。（具体证明参见算法导论P358）。

需要说明的是负权值边和松弛技术。Dijkstra算法是不允许图中存在负权边的，否则无法得到正确的结果。而Bellman-ford算法就允许图中存在负权边，而且该算法可以检测图中是否存在负权回路。两种算法都用到了松弛技术。即对边（u，v），如果通过u到达v比当前找到的到v的最短路径还短，那么就更新d[v]、parent[v]。通过松弛，可以减小最短路径估计。

Bellman-ford算法：

因为图中任意两个顶点的最短路径最多包含|V|-1条边，所以至多对每条边进行|V|-1次松弛后就会得到任意两个顶点间的实际最短路径。如果还能通过松弛降低最短路径估计，那么就可以断定图中存在负权回路，因为如果从s到v的路径中包含负权回路，那么s到v的最短路径长度就是负无穷了。可以这样理解，第i（i>=1）次松弛得到的是源点s到每个顶点vV的路径长度为i的最短路径，第|V|-1次松弛得到的就是长度为|V|-1的最短路径。不过，显然不是每个顶点到s的最短路径长度都是|V|-1，所以对每条边都进行|V|-1次松弛操作是没有必要的。Bellman-ford的时间复杂度为O(VE)。可以对该算法进行简单的优化，如果本次循环并未对任何一条边进行松弛，那么可以判定已经得到了最终结果，退出循环。

如图所示：

代码如下：

[cpp]
#include<iostream>
#include<list>
using namespace std;

#define MAXVALUE 10000          //定义一个最长路径

//此处Prim算法的图为有向图

struct Edge
{
    int verno;          //邻接数组中节点编号
    int weight;         //权值
    Edge* next;         //指向下一条边
};

struct Vertex
{
    Edge *adj;          //所指向的节点所在边
    int verno;          //邻接数组中节点编号
    char key;           //关键字
};

struct Graph
{
    Vertex *vertexs;    //节点数组
    int vertexnum;      //节点个数
    int adjnum;         //边数
};

class MSWBellmanFord
{
public:
    MSWBellmanFord(char *vertex,int vernum,char adj[][2],int *weight,int adjnum);
    void BellmanInsert(int source,int dest,int weight);
    int BellmanFindKey(char key);
    void BellmanInitSingleSource();
    bool BellmanMSW(char sourceKey);
    void BellmanOutput();
private:
    int *swayweight;
    int *parent;
    Graph *bfordGraph;
};

MSWBellmanFord::MSWBellmanFord(char *vertex,int vernum,char adj[][2],int *weight,int adjnum)
{
    int i,source,dest;

    swayweight = new int[vernum];
    parent = new int[vernum];
    bfordGraph = new Graph;

    bfordGraph->vertexs = new Vertex[vernum];
    bfordGraph->adjnum = adjnum;
    bfordGraph->vertexnum = vernum;
    for(i = 0;i < vernum;i++)
    {
        bfordGraph->vertexs[i].key = vertex[i];
        bfordGraph->vertexs[i].verno = i;
        bfordGraph->vertexs[i].adj = NULL;
    }

    for(i = 0;i < adjnum;i++)
    {
        source = BellmanFindKey(adj[i][0]);
        dest = BellmanFindKey(adj[i][1]);
        BellmanInsert(source,dest,weight[i]);
        //BellmanInsert(dest,source,weight[i]);         //无向图与有向图的区别在此
    }
}

void MSWBellmanFord::BellmanInsert(int source,int dest,int weight)
{
    if(bfordGraph->vertexs[source].adj == NULL || bfordGraph->vertexs[source].adj->weight > weight)
    {
        Edge* newnode = new Edge;
        newnode->verno = dest;
        newnode->weight = weight;
        newnode->next = bfordGraph->vertexs[source].adj;
        bfordGraph->vertexs[source].adj = newnode;
    }
    else
    {
        Edge* temp = bfordGraph->vertexs[source].adj;
        while(temp->next != NULL)                        //插入新边的时候，把权值从低到高进行排序
        {
            if(temp->next->weight > weight)
                break;
            temp = temp->next;
        }
        Edge* newnode = new Edge;
        newnode->verno = dest;
        newnode->weight = weight;
        newnode->next = temp->next;
        temp->next = newnode;
    }
}

int MSWBellmanFord::BellmanFindKey(char key)
{
    int i;
    for(i = 0;i < bfordGraph->vertexnum;i++)
    {
        if(bfordGraph->vertexs[i].key == key)
         &nbs

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