图的最短路径

 

交通网络可以画成带权的图，图中顶点表示城市，边代表城市间的公路，边上的权表示公路的长度。对于这样的交通网络常常提出这样的问题：两地之间是否有公路可通？在有几条路可通的情况下，哪一条路最短？以上提出的问题就是在带权图中求最短路径问题，此时路径的长度不是路径上边的数目，而是路径上的边所带权值的总和。
　　设 A 城到 B 城有一条公路， A 城的海拔高于 B 城，若考虑到上坡和下坡的车速不同，则边 和边 上表示行驶时间的权值也不同，即 和 应该是两条不同的边，考虑到交通网络的这种有向性，本节只讨论有向网络的最短路径问题，并假定所有的权为非负实数。习惯上称路径开始顶点为源点，路径的最后一个顶点为终点。
1、最短路径定义
　　所谓最短路径问题是指：如果从图中某一顶点（源点）到达另一顶点（终点）的路径可能不止一条，如何找到一条路径似的沿此路径上各边的权值总和（称为路径长度）达到最小。
2、单源最短路径
    单源最短路径问题：已知有向带权图(简称有向网)G=(V，E)，找出从某个源点s∈V到V中其余各顶点的最短路径。
迪杰斯特拉(Dijkstra)算法求单源最短路径
    由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法。
（1）按路径长度递增序产生各顶点最短路径
    若按长度递增的次序生成从源点s到其它顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看作是已生成的源点到其自身的长度为0的路径）。

（2）具体做法
　　一开始第一组只包括顶点 v 1 ，第二组包括其他所有顶点， v 1 对应的距离值为 0 ，第二组的顶点对应的距离值是这样确定的：若图中有边 , 则 v j 的距离为此边所带的权值，否则 v j 的距离值为一个很大的数 ( 大于所有顶点间的路径长度 ) ，然后每次从第二组的顶点中选一个其距离值为最小的 v m 加入到第一组中。每往第一组加入一个顶点 v m ，就要对第二组的各个顶点的距离值进行一次修正。若加进 v m 做中间顶点，使从 v 1 到 v j 的最短路径比不加 v m 的路径为短，则要修改 v j 的距离值。修改后再选距离最小的顶点加入到第一组中。如此进行下去，直到图中所有顶点都包括在第一组中，或再也没有可加入到第一组中的顶点存在为止。
　　假设有向图 G 的 n 个顶点为 1 到 n, 并用邻接矩阵 cost 表示 , 若 < v i , v j > 是图 G 中的边，则 cost[i][j] 的值等于边所带的权 ; 若 不是图 G 中的边，则 cost[i][j] 等于一个很大的数；若 i=j, 则 cost[i][j]=0 。另外 , 设置三个数组 S[n] 、 dist[n] 、 pre[n] 。 S 用以标记那些已经找到最短路径的顶点，若 S[i-1]=1, 则表示已经找到源点到顶点 i 的最短路径 , 若 S[i-1]=0, 则表示从源点到顶点 i 的最短路径尚未求得。 dist[i-1] 用来记录源点到顶点 i 的最短路径。 pre[i-1] 表示从源点到顶点 i 的最短路径上该点的前趋顶点，若从源点到该顶点无路径，则用 0 作为其前一个顶点序号。
（3）迪杰斯特拉算法

void  DijGraph::ShorttestPath_Dijkstra(int v)
  {     //G是一个具有n个顶点的带权有向图，求从源点v到其余各顶点的最短路径长度
    for(int i=0;i，path，S的初始化
      {  dist[i]=Edge[v][i];S[i]=0;
         if(i!=v&&dist[i]         else path[i]=-1;        //顶点i无前顶点
      }
   S[v]=1;               //顶点v加入已求出的最短路径的顶点集合
   dist[v]=0;
   for(i=0;i求其余n-1个顶点的最短路径
   {float min=MAXNUM;
   int u=v;
   for(int j=0;j选择当前不在集合S中具有最短路径的顶点u
   if(!S[j]&&dist[j]   S[u]=1;        //顶点u加入到已求出最短路径的顶点集合
   for(int w=0;w修改期于顶点的当前最短路径
   if(!S[w]&&Edge[u][w]      { dist[w]=dist[u]+Edge[u][w];
        path[w]=u;}
      }
  }
其他最短路径问题
    　最短路径问题的提法很多，其它的最短路径问题均可用单源最短路径算法予以解决：
　　①单目标最短路径问题(Single-Destination Shortest-Paths Problem)：找出图中每一顶点v到某指定顶点u的最短路径。只需将图中每条边反向，就可将这一问题变为单源最短路径问题，单目标u变为单源点u。
　　②单顶点对间最短路径问题(Single-Pair Shortest-Path Problem)：对于某对顶点u和v，找出从u到v的一条最短路径。显然，若解决了以u为源点的单源最短路径问题，则上述问题亦迎刃而解。而且从数量级来说，两问题的时间复杂度相同。
　　③所有顶点对间最短路径问题(All-Pairs Shortest-Paths Problem)：对图中每对顶点u和v，找出u到v的最短路径问题。这一问题可用每个顶点作为源点调用一次单源最短路径问题算法予以解决。