单源最短路径

问题描述：     

        给定带权有向图G和源点v，求从v到G中各个顶点的最短路径。

    如图1-1所示带权有向图G中从v0到其余各个顶点。

 

V是未找到最短路径的顶点的集合，S表示找到最短路径的顶点的集合。即G中所有的顶点的集合={V， S}}。

首先，引进一个辅助向量D,它的每个量D[i]表示当前所找到的从始点V0到终点Vi的最短路径长度。它的初始值为：若从V0到Vi有弧，则D[i]为弧上的权值;否则置D[i]为∞(用65535表示）。则 

            temp = min {  D[i]   |  Vi ∈ V } && j=i     Vj

找到终点Vj, D[j]表示的就是从V0出发的所有路径中长度最短的一条。此路径为（V0, Vj）。

      那么，拓展到下一跳的最短路径是哪一条呢？假设终点是Vk，S为已求得的最短路径的终点的集合。那么下一条最短路径 或是弧（V0, Vk），或者是中间经过S中的顶点而最后到达终点Vk的路径①。

这个结论可以用反证法证明：假设有一条到达Vk的最短路径既不是弧（V0, Vk）也不经过S中的顶点，则存在一条终点不在S中但长度更短的路径，这与S的定义矛盾。

因此，拓展到下一跳的所有最短路径中长度最短的一条（注意，前面找到一条到终点Vk的最短路径加入S之后，若Vk的下一跳Vx存在且没有加入到S中且Vk->Vx的花费比现有D[x]要小，这里会更新D[x]的值）     

            temp = min {  D[i]   |  Vi ∈ ( V-S) } && j=i

其中，D[j]或者是弧（V0, Vi）上的权值，或者是D[x] (Vx ∈ S)和弧（Vx， Vi）的权值之和。这里用到的就是①的结论。

C语言程序代码：

#include <stdio.h>

#include <stdlib.h>

 

#define FALSE      0

#define TRUE      1

#define NUM      6

#define INIT_VALUE      65535

 

void shortest (void)

{

      int v, w, min, start, S[NUM], D[NUM], i, k;

      int pre[NUM];

 

      int matrix[][NUM] = {      65535, 65535, 10, 65535, 30, 100,

                         65535, 65535, 5, 65535, 65535, 65535,

                         65535, 65535, 65535, 50, 65535, 65535,

                         65535, 65535, 65535, 65535, 65535, 10,

                         65535, 65535, 65535, 20, 65535, 60,

                         65535, 65535, 65535, 65535, 65535, 65535};

      start = 0;

      for (w=0; w<NUM; ++w)//设置空路径

            pre[w] = -1; 

      for (v=0; v<NUM; v++)

      {

            S[v] = FALSE;

            D[v] = matrix[start][v];

            if (D[v]<INIT_VALUE)//设置与起点直连的顶点

                  pre[v] = start;      //所有和起始点直连的顶点初始化其前节点为起始点

      }

      D[start] = 0;//将起点自身加入已找到最短路径集合

      S[start] = TRUE;

      for (i=1; i<NUM; i++)//n-1次循环

      {

            min = INIT_VALUE;

            for (w=0; w<NUM; ++w)

            {

                  if (!S[w])//w顶点在V-S中

                        if (D[w] < min)

                        {

                              v       = w;

                              min      = D[w];

                        }

            }

            S[v] = TRUE;//加入S

            for (w=0; w<NUM; ++w)

                  if (!S[w] && (min+matrix[v][w]) < D[w])//更新D[w]

                  {

                        D[w] = min + matrix[v][w];

                        pre[w] = v;//同时更新pre[w]的值

                  }

      }

      int temp=-2;

      for (i=1; i<NUM; i++)

            if (D[i]<INIT_VALUE)

            {

                  temp = i;

                  while (pre[temp] >= 0)

                  {

                        printf ("V%d ", temp);

                        temp      = pre[temp];

                  }

                  printf ("V%d\n", temp);

            }

      printf ("\n", pre[0]);  

}

main ()

{

      shortest();

}

在我QQ空间上也有：http://user.qzone.qq.com/1475032202/2