1.每一对顶点间的最短路径

如果要计算每一对顶点之间的最短路径，需每次以一个顶点为出发点，将迪杰斯特拉算法重复执行n次，就可以得到每一对顶点的最短路径，总的时间复杂度为 O(n3) 。如果采用弗洛伊德算法，虽然时间复杂度也是 O(n3) ，但是形式更简单。

2.弗洛伊德算法

基本算法思想：假设求顶点 vi 到顶点 vj 的最短路径，如果从顶点 vi 到 vj 有弧，则从 vi 到 vj 存在一条成都为arc[i][j]的路径，但该路径不一定是 vi 到 vj 的最短路径，还需要进行n次试探。首先需要从顶点 v0 开始，如果有路径 (vi,v0,vj) 存在，则比较路径 (vi,vj) 和 (vi,v0,vj) ，选择两者中最短的一个且中间顶点的序号不大于0的最短路径。
假如在路径上再增加一个顶点 v1 ，如果 (vi,…,v1) 和 (v1,…,vj) 分别是当前找到的中间顶点的序号不大于0 的最短路径，那么 (vi,…，v1…vj) 就有可能是从 vi 到 vj 的中间顶点的序号不大于1的最短路径。把它和已经得到的从 vi 和 vj 中间顶点序号不大于0的最短路径相比较，从中选择中间顶点的序号不大于1的最短路径之后，再增加1个顶点 v2 ，继续进行试探。
依此类推，一般情况下，若 (vi,…,vk) 和 (vk,…,vj) 分别是从 vi 到 vk 和从 vk 到 vj 的中间顶点的序号不大于k-1的最短路径，则将 (vi,…，vk…vj) 和已经得到的从 vi 到 vj 且中间顶点序号不大于k-1的最短路径相比较，其长度较短者就是从 vi 到 vj 的中间顶点序号不大于k的最短路径。经过n次比较，可以得到从 vi 到 vk 的中间顶点序号不大于n-1的最短路径。依照这种方法，可以得到各个顶点之间的最短路径。

假设采用邻接矩阵存储带权有向图G，则各个顶点之间的最短路径可以保存在一个n阶方阵D中，每次求出的最短路径可以用矩阵表示为 D−1、D0、D1、D2、…、Dn−1 。其中， D−1[i][j]=G.arc[i][j].adj ， Dk[i][j]=Min{Dk−1[i][j],Dk−1[i][k]|0≤k≤n−1} 。其中， Dk[i][j] 即为从顶点 vi 到 vk 的最短路径长度。

3.弗洛伊德算法的实现

类型定义

#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<stdlib.h>
#define INFINITY 65535 /*定义一个无限大的值*/
#define MaxSize 50 /*最大顶点个数*/
typedef char VertexType[4];
typedef char InfoPtr;
typedef int VRType;
typedef enum{DG,DN,UG,UN}GraphKind;     /*图的类型：有向图、有向网、无向图和无向网*/
typedef int PathMatrix[MaxSize][MaxSize][MaxSize];  /*定义一个保存最短路径的三维数组*/
typedef int ShortPathLength[MaxSize][MaxSize];      /*定义一个保存从顶点v到顶点w的最短距离的数组*/
typedef struct
{
 VRType adj; /*对于无权图，用1表示相邻，0表示不相邻；对于带权图，存储权值*/
 InfoPtr *info; /*与弧或边的相关信息*/
}ArcNode,AdjMatrix[MaxSize][MaxSize];
typedef struct                  /*图的类型定义*/
{
 VertexType vex[MaxSize]; /*用于存储顶点*/
 AdjMatrix arc; /*邻接矩阵，存储边或弧的信息*/
 int vexnum,arcnum; /*顶点数和边（弧）的数目*/
 GraphKind kind; /*图的类型*/
}MGraph;
typedef struct                  /*添加一个存储网的行、列和权值的类型定义*/
{
 int row;
 int col;
 int weight;
}GNode;

Floyd算法

void Floyd(MGraph N,PathMatrix path,ShortPathLength dist)
/*用Floyd算法求有向网N的各顶点v和w的最短路径， 其中path[v][w][u]表示u是从v到w当前求得最短路径上的顶点*/
{
    int u,v,w,i;
    for(v=0;v<N.vexnum;v++)                 /*初始化数组path和dist*/
        for(w=0;w<N.vexnum;w++)
        {
            dist[v][w]=N.arc[v][w].adj;     /*初始时，顶点v到顶点w的最短路径为v到w的弧的权值*/
            for(u=0;u<N.vexnum;u++)
                path[v][w][u]=0;            /*路径矩阵初始化为零*/
            if(dist[v][w]<INFINITY)          /*如果v到w有路径，则由v到w的路径经过v和w两点*/
            {
                path[v][w][u]=1;
                path[v][w][w]=1;
            }
        }
    for(u=0;u<N.vexnum;u++)
        for(v=0;v<N.vexnum;v++)
            for(w=0;w<N.vexnum;w++)
                if(dist[v][u]<INFINITY&&dist[u][w]<INFINITY&&dist[v][u]+dist[u][w]<dist[v][w])
                /*从v经u到w的一条路径为当前最短的路径*/
                {
                    dist[v][w]=dist[v][u]+dist[u][w];   /*更新v到w的最短路径*/
                    for(i=0;i<N.vexnum;i++)             /*从v到w的路径经过从v到u和从u到w的所有路径*/
                        path[v][w][i]=path[v][u][i]||path[u][w][i];
                }
}

邻接矩阵创建有向网

void CreateGraph(MGraph *N,GNode *value,int vnum,int arcnum,VertexType *ch)
/*采用邻接矩阵表示法创建有向网N*/
{
    int i,j,k;
    N->vexnum=vnum;
    N->arcnum=arcnum;
    for(i=0;i<vnum;i++)             /*将各个顶点赋值给vex域*/
        strcpy(N->vex[i],ch[i]);
    for(i=0;i<N->vexnum;i++)            /*初始化邻接矩阵*/
        for(j=0;j<N->vexnum;j++)
        {
            N->arc[i][j].adj=INFINITY;
            N->arc[i][j].info=NULL; /*弧的信息初始化为空*/
        }
    for(k=0;k<arcnum;k++)
    {
        i=value[k].row;
        j=value[k].col;
        N->arc[i][j].adj=value[k].weight;
    }

    N->kind=DN;                     /*图的类型为有向网*/
}

输出图

void DisplayGraph(MGraph N)
/*输出邻接矩阵存储表示的图N*/
{
    int i,j;
    printf("有向网具有%d个顶点%d条弧，顶点依次是: ",N.vexnum,N.arcnum);
    for(i=0;i<N.vexnum;++i)             /*输出网的顶点*/
        printf("%s ",N.vex[i]);
    printf("\n有向网N的:\n");               /*输出网N的弧*/
    printf("序号i=");
    for(i=0;i<N.vexnum;i++)
        printf("%8d",i);
    printf("\n");
    for(i=0;i<N.vexnum;i++)
    {
        printf("%8d",i);
        for(j=0;j<N.vexnum;j++)
            printf("%8d",N.arc[i][j].adj);
        printf("\n");
    }
}

主程序

void main()
{
    int i,j,vnum=6,arcnum=8;
    MGraph N;
    GNode value[]={{0,2,15},{0,4,30},{0,5,100},{1,2,10},
    {2,3,50},{3,5,10},{4,3,20},{5,4,60}};
    VertexType ch[]={"v0","v1","v2","v3","v4","v5"};
    PathMatrix path;                        /*用二维数组存放最短路径所经过的顶点*/
    ShortPathLength dist;                   /*用一维数组存放最短路径长度*/
    CreateGraph(&N,value,vnum,arcnum,ch); /*创建有向网N*/
    DisplayGraph(N);                        /*输出有向网N*/
    Floyd(N,path,dist);
    for(i=0;i<N.vexnum;i++)
    {
        for(j=i+1;j<N.vexnum;j++)
        printf("%s到%s的最短路径长度为：%d\n",N.vex[i],N.vex[j],dist[i][j]);
    }
}

测试结果

秒客网

【笔记】每一对顶点间的最短路径

1.每一对顶点间的最短路径

2.弗洛伊德算法

3.弗洛伊德算法的实现

相关文章