最短路径

在一个不带权图中，若从一顶点到另一顶点存在着一条路径 ，则称该路径长度为该路径上所经过的边的数目，它等于该路径上的顶点数减 1 ,由于从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，把路径长度最短（即经过的边数最少）的那条路径称为最短路径, 其长度称为最短路径长度或最短距离。

对于带权图，考虑路径上各边上的权，则把一条路径上所经边的权之和定义为该路径的路径长度。从源点到终点可能有不止一条路径，把路径长度最小 的那条路径称为最短路径。其路径长度（权之和）称为最短路径长度。

实际上，只要把不带权图上的每条边看成是权值为 1 的边，那么不带权图和带权图的最短路径和最短距离的定义就一致了。求图的最短路径有两个方面的问题，即求图中某一顶点到其余各顶点的最短路径和求图中每对顶之间的最短路径。

单源最短路径

问题：给定一个带权有向图 G 与源点 v , 求从源点 v 到 G 中其他顶点的最短路径，并限定各边上的权值大 0 。 采用狄克斯特拉算法求解，其基本思想，设 G=(V,E) 是一个带权有向图，把图中的顶点集合分成两组，第一组为己求出最短路径的顶点集合（用 S 表示，初始时 S 只有 1 个源点 ，以后每求得一条最短路径v,…,u , 就将顶点 u 加入到集合 S 中，直到全部顶点都加入到 S 中，算法就结束了），第 2 组为其余未确定最短路径的顶点集合（用 U 表示），按最短路径长度的递增次序依次把第 2 组的顶点加入 S中。

Dijstra 算法的具体步骤如下:

(1) 初始时 S 只包含源点，即 S={v} , 源点 v 到 U 距离为 0 。 U 包含除源点 v 以外的其他顶点，源点 v 到 U 中任一顶点 i 的最短路径长度为边上的权（若源点 v→i 有边<v,i>)或 ∞（若源点 v→ 没有边）

(2) 从 U 中选取个顶点 u 。 使源点 v→u 的最短路径长度为最小，然后把顶点 u 加入 S 中。

(3) 以顶点 u 为新考虑的中间点，修改源点 v 到 U 中所有顶点的最短路径长度，称之为路径调整，其过程如图所示（图中顶点之间的实线箭头表示边，虚线箭头表示路径），对于 U 中的某个顶点 j 在没有考虑中间点 u 时，假设求得从源点 v→j 的一条最短径为 （v,…,a,j) ，其最短路径为 c~vj~（如果没有这样的最短路径,cvj=∞），而从源点 v→u 的一条最短路径路径为 （v,…,u), 其最短路径长度为c~vu~ 。现在考虑中间点 u ,假设从源点 v→j 存在另一条经过顶点 的路径（其中顶点 u 到顶点 j 有 一条边），其路径长为 c~vu~+w~uj~。这样在考虑中间点 u 以后，从源点 → 有两条路径：

• 经过顶点 u 的路径路径长度为 c~vu~+w~uj~。

• 不经过顶点 u 的原来的最短路径，路径长度为 c~vj~。 显然，在考虑中间点 u 以后， 源点 v→j 的最短路径是上述两条路径中的较短者。也就是说，源点 v→ 的最短路径长度调整为 MIN{c~vu~+w~uj~,c~vj~}。

(4) 重复步骤 (2) (3) 直到 S 包含所有的顶点。

每对顶点之间的最短路径

问题： 对于一个各边权值均大于零的有向图，对每一对顶点 i\=j ，求出顶点 i 与顶点 j 之间的最短路径和最短路径长度。 可以通过以每个顶点作为源点循环求出每对顶点之间的最短路径。除此之外，弗洛伊德(Floyd) 算法也可用于求两顶点之间的最短路径。 假设有向图 G=(V,E) 采用邻接矩阵 g 表示，另外设置一个二维数组用于存放当前顶点之间的最短路径长度，即分量 A【i】【j】 表示当前 i→j 的最短路径长度。Floyd 算法的基本思想是递推产生一个矩阵序 A0,A1,…,Ak,…,An, 其中 Ak【i】【j】 表示 i→j 的路径上所经过的顶点编号不大于 k 的最短路径长度。

初始时有 A−1【i】【j】=g.edges【i】【j】。若 Ak−1【i】【j】 已求出，现在考察顶点 k 。求 i→j 的路径上所经过顶点编号不大于 k 的最短路径 Ak【i】【j】,此时的 i→j 路径有两条。

路径 1 : 在考查顶点 k 之前求出其最短路径长度为 Ak−1【i】【j】 (若没有这样的路径，取值为 ∞)

路径 2 : 考查顶点 k , i→j 存在一条经过顶点 k 的路径， 的路径，如图 2 所示，该路径分为两段，即 i→k 和k→j，其长度为 Ak−1【i】【k】+Ak−1【k】【j】（若没有这样的路径，该长度取值为 ∞） 显然，如果路径 2 的长度更短，即 Ak−1【i】【k】+Ak−1【k】【j】<Ak−1【i】【j】 ，则取经过顶点 k 的路径为新的最短路径。

归纳起来, floyed 算法思想的描述如下： A−1【i】【j】=g.edges【i】【j】

Ak【i】【j】=MIN{Ak−1【i】【k】+Ak−1【k】【j】,Ak−1【i】【j】}(0≤k≤n−1)

上式是一个迭代表达式，每迭代一次，i→j 的最短路径上就多考虑了一个顶点；经过 n 次迭代后所得的 An−1【i】【j】 的值就是考虑所有顶点后 i→j 的最短路径，就是最终解。 另外用二维数组 path 保存最短路径，它与当前迭代的次数有关。 pathk【i】【j】 存放着考查顶点 0,1,…,k 之后得到的 i→j 的最短路径中顶点 j 的前一个顶点编号，这和 Dijstra 算法中采用的方式相似。 初始时尚未考查任何顶点，若 i→j 有边 <i,j＞ ，将该边看成是 i→j 的最短路径，该路径上顶点 j 的前一个顶点 i 所以置 path−1【i】【j】=i, path−1【i】【j】=−1 (表示无路径）。

考虑顶点 k 之前，i→j 的最短路径是 (i,…,b,j)，即pathk−1【i】【j】=b ,k→j 的最短路径是 (k,…,a,j)，即pathk−1【k】【j】=a

考虑顶点 k 的调整情况如图 3 所示（图中虚线箭头表示路径，实线箭头表示边）：若经过顶点 k 的路径较长，则 Ak【i】【j】=Ak−1【i】【j】，不需要修改路径；若经过顶点 k 的路径较短，则需要修改最短路径和路径长度，Ak【i】【j】=Ak−1【i】【k】+Ak−1【k】【j】,path【i】【j】=a=pathk−1【k】【j】。

在算法结束时，由二维数组 path 的值追溯，可以得到从 i→j 的最短路径。

#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
#define INF 32767    /*INF表示∞*/
#define    MAXV 100    /*最大顶点个数*/
typedef int InfoType;

typedef struct
{
    int no;                        /*顶点编号*/
    InfoType info;                /*顶点其他信息*/
} VertexType;                    /*顶点类型*/
typedef struct                  /*图的定义*/
{
    int edges[MAXV][MAXV];         /*邻接矩阵*/
    int n,e;                       /*顶点数,弧数*/
    VertexType vexs[MAXV];        /*存放顶点信息*/
} MGraph;
void Ppath(int path[][MAXV],int i,int j);  /*前向递归查找路径上的顶点*/
void Dispath(int A[][MAXV],int path[][MAXV],int n);
void Floyd(MGraph g);
void Ppath(int path[][MAXV],int i,int j)  /*前向递归查找路径上的顶点*/
{
    int k;
    k=path[i][j];
    if (k==-1) return;    /*找到了起点则返回*/
    Ppath(path,i,k);    /*找顶点i的前一个顶点k*/
    printf("%d,",k);
    Ppath(path,k,j);    /*找顶点k的前一个顶点j*/
}
void Dispath(int A[][MAXV],int path[][MAXV],int n)
{
    int i,j;
    for (i=0;i<n;i++)
        for (j=0;j<n;j++)
    {
        if (A[i][j]==INF)
        {
            if (i!=j)
                printf("从%d到%d没有路径\n",i,j);
        }
        else
        {
            printf("  从%d到%d=>路径长度:%d 路径:",i,j,A[i][j]);
            printf("%d,",i);    /*输出路径上的起点*/
            Ppath(path,i,j);    /*输出路径上的中间点*/
            printf("%d\n",j);    /*输出路径上的终点*/
        }
    }
}
void Floyd(MGraph g)
{
    /********** Begin **********/
    int A[MAXV][MAXV],path[MAXV][MAXV];  
    int i,j,k;  
    for (i=0; i<g.n; i++)  
        for (j=0; j<g.n; j++)  
    {  
        A[i][j]=g.edges[i][j];  
        path[i][j]=-1;  
    }  
    for (k=0; k<g.n; k++)  
    {  
        for (i=0; i<g.n; i++)  
            for (j=0; j<g.n; j++)  
                if (A[i][j]>A[i][k]+A[k][j])  
        {  
            A[i][j]=A[i][k]+A[k][j];  
            path[i][j]=k;  
        }  
    }  
    Dispath(A,path,g.n);   //输出最短路径  

    /********** End **********/
}int main()
{
    int i,j;
    MGraph g;
    int n,e;
    int a[MAXV][MAXV];
    scanf("%d %d",&n,&e);
    g.n=n;g.e=e;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for (i=0;i<g.n;i++)        
        for (j=0;j<g.n;j++)
            g.edges[i][j]=a[i][j];
    printf("各顶点的最短路径:\n");
    Floyd(g);
    return 0;
}/*
测试数据:
4 8
0 5 32767 7
32767 0 4 2
3 3 0 2
32767 32767 1 0
测试结果:
各顶点的最短路径:
  从0到0=>路径长度:0 路径:0,0
  从0到1=>路径长度:5 路径:0,1
  从0到2=>路径长度:8 路径:0,3,2
  从0到3=>路径长度:7 路径:0,3
  从1到0=>路径长度:6 路径:1,3,2,0
  从1到1=>路径长度:0 路径:1,1
  从1到2=>路径长度:3 路径:1,3,2
  从1到3=>路径长度:2 路径:1,3
  从2到0=>路径长度:3 路径:2,0
  从2到1=>路径长度:3 路径:2,1
  从2到2=>路径长度:0 路径:2,2
  从2到3=>路径长度:2 路径:2,3
  从3到0=>路径长度:4 路径:3,2,0
  从3到1=>路径长度:4 路径:3,2,1
  从3到2=>路径长度:1 路径:3,2
  从3到3=>路径长度:0 路径:3,3
*/