算法笔记-----单源最短路径之Bellman-Ford算法

今天介绍一种计算单源最短路径的算法Bellman-Ford算法，对于图G=(V,E)来说，该算法的时间复杂度为O(VE)，其中V是顶点数，E是边数。Bellman-Ford算法适用于任何有向图，并能报告图中存在负环路（边的权重之和为负数的环路，这使得图中所有经过该环路的路径的长度都可以通过反复行走该环路而使路径长度变小，即没有最短路径）的情况。以后会介绍运行速度更快，但只适用于没有负权重边的图中的Dijkstra算法。Dijkstra算法可以参考我的下一篇博客单源最短路径之Dijkstra算法

在介绍Bellman-Ford算法之前，先介绍在计算图的单源最短路径的各种算法中都会用到的松弛操作。

 1 // 松弛操作，检查<s, ..., v>的距离是否比<s, ..., u, v>大，是则更新<s, ..., v>为<s, ..., u, v>
 2 void relax(Vertex *u, Vertex *v, int w)
 3 {
 4     if (u->weight == INF || w == INF)    return;
 5     if (v->weight > u->weight + w)
 6     {
 7         v->weight = u->weight + w;
 8         v->p = u;
 9     }
10 }

Vertex是顶点的数据类型，<u,v>是图G中的一条边。顶点Vertex的属性weight记录了该顶点当前距离源点的最短距离，p记录了顶点在其最短距离中的前一个顶点。松弛操作要做的工作就是检查路径<s,...,v>的距离是否比<s,...,u,v>大，是则更新之，并把s到v的距离修改为s到u的距离加上<u,v>的长度，其中<s,...,v>为源点s到顶点v的原来的路径，<s,...,u>为源点s到顶点u的路径。 Bellman-Ford算法的思想就是反复对图G中的边<u,v>进行松弛操作，知道所有顶点到s的距离都被最小化为止。这里的图使用邻接表表示，下面给出图的定义和算法程序，Bellman-Ford算法需要的参数包括图g、权重矩阵w和源点编号s（顶点编号从1开始）。

 1 typedef struct GNode
 2 {
 3     int number;    // 顶点编号
 4     struct GNode *next;
 5 } GNode;
 6 
 7 typedef struct Vertex
 8 {
 9     int number;
10     int weight;        // 该顶点到源点的距离
11     struct Vertex *p;
12 } Vertex;
13 
14 typedef struct Graph
15 {
16     GNode *LinkTable;
17     Vertex *vertex;
18     int VertexNum;
19 } Graph;

 1 /**
 2 * Bellman Ford 单源最短路径算法
 3 * @return true 没有负环路； false 有负环路，最短路径构造失败
 4 */
 5 bool Bellman_Ford(Graph *g, int **w, int s)
 6 {
 7     initialize(g, s);
 8 
 9     GNode *linkTable = g->LinkTable;
10     for (int i = 1; i < g->VertexNum; i++)
11     {
12         // 反复将边加入到已有的最小路径图中，检查是否有更优路径
13         for (int j = 0; j < g->VertexNum; j++)
14         {
15             GNode *node = (linkTable + j)->next;
16             Vertex *u = g->vertex + j;
17             while (node != NULL)
18             {
19                 Vertex *v = g->vertex + node->number - 1;
20                 int weight = *((int*)w + j * g->VertexNum + node->number - 1);
21                 relax(u, v, weight);
22                 node = node->next;
23             }
24         }
25     }
26 
27     // 通过检查是否都已达到最短路径来检查是否存在负环路
28     for (int j = 0; j < g->VertexNum; j++)
29     {
30         GNode *node = (linkTable + j)->next;
31         Vertex *u = g->vertex + j;
32         while (node != NULL)
33         {
34             Vertex *v = g->vertex + node->number - 1;
35             int weight = *((int*)w + j * g->VertexNum + node->number - 1);
36             if (v->weight > u->weight + weight)
37             {
38                 return false;
39             }
40             node = node->next;
41         }
42     }
43     return true;
44 }

 1 void initialize(Graph *g, int s)
 2 {
 3     Vertex *vs = g->vertex;
 4     for (int i = 0; i < g->VertexNum; i++)
 5     {
 6         Vertex *v = vs + i;
 7         v->p = NULL;
 8         v->weight = INF;
 9     }
10     (vs + s - 1)->weight = 0;
11 }

上述算法代码实现的Bellman-Ford算法进行了V次对所有边的松弛操作，这是考虑到了最坏情况，假设图G是一条单链，则从表头s到表尾的路径计算需要进行V次松弛操作。下面给出一个演示例子。

 1     Graph graph;
 2     graph.VertexNum = 5;
 3     Vertex v[5];
 4     Vertex v1; v1.number = 1; v1.p = NULL; v[0] = v1;
 5     Vertex v2; v2.number = 2; v2.p = NULL; v[1] = v2;
 6     Vertex v3; v3.number = 3; v3.p = NULL; v[2] = v3;
 7     Vertex v4; v4.number = 4; v4.p = NULL; v[3] = v4;
 8     Vertex v5; v5.number = 5; v5.p = NULL; v[4] = v5;
 9     graph.vertex = v;
10 
11     GNode nodes[5];
12     GNode n1; n1.number = 1;
13     GNode n2; n2.number = 2;
14     GNode n3; n3.number = 3;
15     GNode n4; n4.number = 4;
16     GNode n5; n5.number = 5;
17     GNode a; a.number = 2; GNode b; b.number = 4; n1.next = &a; a.next = &b; b.next = NULL;
18     GNode c; c.number = 3; GNode x; x.number = 4; GNode z; z.number = 5; n2.next = &c; c.next = &x; x.next = &z; z.next = NULL;
19     GNode d; d.number = 2; n3.next = &d; d.next = NULL;
20     GNode f; f.number = 5; GNode g; g.number = 3; n4.next = &f; f.next = &g; g.next = NULL;
21     GNode h; h.number = 1; GNode i; i.number = 3; n5.next = &h; h.next = &i; i.next = NULL;
22     nodes[0] = n1;
23     nodes[1] = n2;
24     nodes[2] = n3;
25     nodes[3] = n4;
26     nodes[4] = n5;
27     graph.LinkTable = nodes;
28 
29     int w[5][5] = { 0,        6,            INF,        7,        INF,
30                     INF,    0,            5,            8,        -4,
31                     INF,    -2,            0,            INF,    INF,
32                     INF,    INF,        -3,            0,        9,
33                     2,        INF,        7,            INF,    0 };
34     int s = 1;
35     if (Bellman_Ford(&graph, (int **)w, s))
36     {
37         for (int i = 0; i < graph.VertexNum; i++)
38         {
39             if (i != s - 1)
40             {
41                 Vertex *v = graph.vertex + i;
42                 printf("路径长度为%d , 路径为 : ", v->weight);
43                 while (v->p != NULL)
44                 {
45                     printf("%d <- ", v->number, v->p->number);
46                     v = v->p;
47                 }
48                 printf("%d
", s);
49             }
50         }
51     }

上面的例程构建的图如下图所示。

Bellman-Ford算法运行过程中各顶点v到源点s=1的距离变化如下所示。

0 INF INF INF INF

0 6 4 7 2

0 2 4 7 2

0 2 4 7 -2

以顶点1到顶点2的路径变化为例，对应上面距离变化的顺序，如下所示。

无路径 ---> <1,2> ---> <1,4,3,2> ---> <1,4,3,2>

算法运行的最终结果如下图所示。

    Graph graph;
   graph.VertexNum = 5;
   Vertex v[5];
   Vertex v1; v1.number = 1; v1.p = NULL; v[0] = v1;
   Vertex v2; v2.number = 2; v2.p = NULL; v[1] = v2;
   Vertex v3; v3.number = 3; v3.p = NULL; v[2] = v3;
   Vertex v4; v4.number = 4; v4.p = NULL; v[3] = v4;
   Vertex v5; v5.number = 5; v5.p = NULL; v[4] = v5;
   graph.vertex = v;

   GNode nodes[5];
   GNode n1; n1.number = 1;
   GNode n2; n2.number = 2;
   GNode n3; n3.number = 3;
   GNode n4; n4.number = 4;
   GNode n5; n5.number = 5;
   GNode a; a.number = 2; GNode b; b.number = 4; n1.next = &a; a.next = &b; b.next = NULL;
   GNode c; c.number = 3; GNode x; x.number = 4; GNode z; z.number = 5; n2.next = &c; c.next = &x; x.next = &z; z.next = NULL;
   GNode d; d.number = 2; n3.next = &d; d.next = NULL;
   GNode f; f.number = 5; GNode g; g.number = 3; n4.next = &f; f.next = &g; g.next = NULL;
   GNode h; h.number = 1; GNode i; i.number = 3; n5.next = &h; h.next = &i; i.next = NULL;
   nodes[0] = n1;
   nodes[1] = n2;
   nodes[2] = n3;
   nodes[3] = n4;
   nodes[4] = n5;
   graph.LinkTable = nodes;

   int w[5][5] = { 0,       6,           INF,       7,       INF,
                   INF,   0,           5,           8,       -4,
                   INF,   -2,           0,           INF,   INF,
                   INF,   INF,       -3,           0,       9,
                   2,       INF,       7,           INF,   0 };
   int s = 1;
   if (Bellman_Ford(&graph, (int **)w, s))
   {
       for (int i = 0; i < graph.VertexNum; i++)
       {
           if (i != s - 1)
           {
               Vertex *v = graph.vertex + i;
               printf("路径长度为%d , 路径为 : ", v->weight);
               while (v->p != NULL)
               {
                   printf("%d <- ", v->number, v->p->number);
                   v = v->p;
               }
               printf("%d ", s);
           }
       }
   }