数算---最短路径

作者: Lcr111 | 来源:发表于2023-05-30 09:05 被阅读0次

最短路径
图的应用-最短路径求解
最短路径之 Bellman 算法
Floyd-Warshall 全源最短路径算法
据结构与算法学习-最短路径
最短路径问题概述
数据结构与算法-最短路径
codeforces-3A Shortest path of t
5. Floyd算法
Java实现广度优先算法-找出图中两个节点的最短路径。

前言

最短路径也是数据结构与算法中常见的问题，不同于最小生成树，最短路径问题则是需要找出起点到终点之间路途最短的路径，属于路径规划范畴的问题了。本篇文章将介绍两种最短路径的算法。
示例：如下图所示，找出V0到V8两点间距离最短的路径。

示例

迪杰斯特拉[Dijkstra]算法

邻接矩阵如下图所示：

思路：

初始化三个数组，final数组用于记录V0到Vw之间最短路径是否有结果，final[w] = 1；D数组表示V0到某个顶点Vw的路径；P数组表示各个顶点的前驱顶点的下标。
从V1开始，V8结束，利用k为当前顶点下标，循环遍历，每一次循环判断当前顶点到其余顶点最小路径。首先判断final数组中是否已经有结果，final[w] = 1，则跳过，final[w] = 0,则比较此时V0-->Vw之间距离最小值与邻接矩阵中arc[k][w] 的和 D[w]的大小，取较小者设为D[w]的值。即V0到Vw的最短距离。（条件：!final[0~9] && min + G.arc[k][w] < D[w]）

执行过程：

初始化三个数组，默认final数组全为0，D数组为邻接矩阵第一行数据，代表V0到连接顶点的已知距离（并非最小距离），P数组值全为0。
从0开始，则(D)[v0] = 0，V0到V0距离为0; final[v0] = 1，表示V0到V0没有路径; (P)[v0] = -1，V0到V0没有路径，所以前驱顶点下标为-1;
来到V1顶点，k = 1, min = 1, 首先判断final[0~9]的情况，再判断min + G.arc[k][w] < D[w]条件是否满足，满足则将对应P[w]位置的值设为k，即前驱顶点为V1。
按照以上步骤k范围[0~8]，min 为当前D[k]的值，然后进行比对，最终得到如下结果：

最终所有的顶点都经过了。此时final数组全为1，D数组中表示V0到其余顶点最短的路径值，P数组则是表示每个顶点的前驱顶点下标。
V0--->V3： 4-->2-->1-->0 最短路径值为7
V0--->V6: 3-->4-->2-->1-->0 最短路径值为10

代码实现

#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535

typedef int Status;
typedef struct
{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

/*用于存储最短路径下标的数组*/
typedef int Patharc[MAXVEX];
/*用于存储到各点最短路径权值的和*/
typedef int ShortPathTable[MAXVEX];

/*10.1 创建邻近矩阵*/
void CreateMGraph(MGraph *G)
{
    int i, j;
    
    G->numEdges=16;
    G->numVertexes=9;
    
    for (i = 0; i < G->numVertexes; i++)
    {
        G->vexs[i]=i;
    }
    
    for (i = 0; i < G->numVertexes; i++)
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITYC;
        }
    }
    
    G->arc[0][1]=1;
    G->arc[0][2]=5;
    G->arc[1][2]=3;
    G->arc[1][3]=7;
    G->arc[1][4]=5;
    
    G->arc[2][4]=1;
    G->arc[2][5]=7;
    G->arc[3][4]=2;
    G->arc[3][6]=3;
    G->arc[4][5]=3;
    
    G->arc[4][6]=6;
    G->arc[4][7]=9;
    G->arc[5][7]=5;
    G->arc[6][7]=2;
    G->arc[6][8]=7;
    
    G->arc[7][8]=4;
    
    
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
    
}

/*10.2 求得网图中2点间最短路径
 Dijkstra 算法
 G: 网图;
 v0: V0开始的顶点;
 p[v]: 前驱顶点下标;
 D[v]: 表示从V0到V的最短路径长度和;
 */
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{
    int v,w,k,min;
    k = 0;
    /*final[w] = 1 表示求得顶点V0~Vw的最短路径*/
    int final[MAXVEX];
    
    /*1.初始化数据*/
    for(v=0; v<G.numVertexes; v++)
    {
        //全部顶点初始化为未知最短路径状态0
        final[v] = 0;
        //将与V0 点有连线的顶点最短路径值;
        (*D)[v] = G.arc[v0][v];
        //初始化路径数组p = 0;
        (*P)[v] = 0;
    }
    
    //V0到V0的路径为0
    (*D)[v0] = 0;
    //V0到V0 是没有路径的.
    final[v0] = 1;
    //v0到V0是没有路径的
    (*P)[v0] = -1;
    
  
    
    //2. 开始主循环,每次求得V0到某个顶点的最短路径
    for(v=1; v<G.numVertexes; v++)
    {
        
        //当前所知距离V0顶点最近的距离
        min=INFINITYC;
        /*3.寻找离V0最近的顶点*/
        for(w=0; w<G.numVertexes; w++)
        {
            if(!final[w] && (*D)[w]<min)
            {
                k=w;
                //w顶点距离V0顶点更近
                min = (*D)[w];
            }
        }
        
        //将目前找到最近的顶点置为1;
        final[k] = 1;
        
        /*4.把刚刚找到v0到v1最短路径的基础上,对于v1 与 其他顶点的边进行计算,得到v0与它们的当前最短距离;*/
        for(w=0; w<G.numVertexes; w++)
        {
            //如果经过v顶点的路径比现在这条路径长度短,则更新
            if(!final[w] && (min + G.arc[k][w]<(*D)[w]))
            {
                //找到更短路径, 则修改D[W],P[W]
                //修改当前路径的长度
                (*D)[w] = min + G.arc[k][w];
                (*P)[w]=k;
            }
        }
    }
}

int main(void)
{
    printf("最短路径-Dijkstra算法\n");
    int i,j,v0;
    MGraph G;
    Patharc P;
    ShortPathTable D;
    v0=0;
    
    CreateMGraph(&G);
    
    ShortestPath_Dijkstra(G, v0, &P, &D);
    
    printf("最短路径路线:\n");
    for(i=1;i<G.numVertexes;++i)
    {
        printf("v%d -> v%d : ",v0,i);
        j=i;
        while(P[j]!=-1)
        {
            printf("%d ",P[j]);
            j=P[j];
        }
        printf("\n");
    }
    
    printf("\n最短路径权值和\n");
    for(i=1;i<G.numVertexes;++i)
        printf("v%d -> v%d : %d \n",G.vexs[0],G.vexs[i],D[i]);
    
    printf("\n");
    return 0;
}

弗洛伊德[Floyd]算法

这种算法的大致含义就是利用中间过顶点K，计算出顶点V到顶点W(W=[0~8])之间的最短路径，利用邻接矩阵G，比较D[v][w] 和 D[v][k] + D[k][w] 之间的大小，更新二维数组D，并且利用二维数组P记下此时的k,公式如下：

D[v][w] = min{ D[v][w], D[v][k] + D[k][w] }

利用实时更新的二维数组D和一个记录顶点下标k的二维数组P来记录算法中涉及的信息。

以上是D数组和P数组默认初始值。

演算过程

k = 0 , v 的范围[0~8], w的范围 [0~8], 意思就是以V0顶点为中转点，比较此时D[v][w] 与 D[v][0]+ D[0][w] 的大小，发现并没有任何变化，D[v][w] < （D[v][0]+ D[0][w]）
k = 1, v 的范围[0~8], w的范围 [0~8]，意思就是以V1顶点为中转点，比较此时D[v][w] 与 D[v][0]+ D[0][w] 的大小，一圈比较下来，得到如下结果：

k=1

如上图中的结果，相应的也需要更改P数组红色区域值为1，如下所示：

k=1
k 由 2 -> 8, v 的范围[0~8], w的范围 [0~8]，意思就是以V1顶点为中转点，比较此时D[v][w] 与 D[v][0]+ D[0][w] 的大小，由此循环比较，最终得到的最终结果如下：

最终结果

如上图最终结果可知，D数组第一行即V0到各个顶点的最小距离，结果与上方第一种方法结果一样：

那么V0到各个顶点最短距离求出来了，但是怎么知道V0到各个顶点最短距离是怎么走的，例如V0-V8 经过哪些顶点呢？

解答：以V0～V8为例，从P数组中看出，P[0][8] = 1, 说明经过顶点V1，将1替代0，P[1][8] = 2，说明经过顶点2，再将2替代1得到P[2][8] = 4, 则表示经过顶点4，依次类推，最终经过定顶点情况为：V0->V1->V2->V4->V3->V6->V7->V8

代码实现

#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */

typedef struct
{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];

/* 11.1 构成邻近矩阵 */
void CreateMGraph(MGraph *G)
{
    int i, j;
    
    /* printf("请输入边数和顶点数:"); */
    G->numEdges=16;
    G->numVertexes=9;
    
    for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    {
        G->vexs[i]=i;
    }
    
    for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITYC;
        }
    }
    
    G->arc[0][1]=1;
    G->arc[0][2]=5;
    G->arc[1][2]=3;
    G->arc[1][3]=7;
    G->arc[1][4]=5;
    
    G->arc[2][4]=1;
    G->arc[2][5]=7;
    G->arc[3][4]=2;
    G->arc[3][6]=3;
    G->arc[4][5]=3;
    
    G->arc[4][6]=6;
    G->arc[4][7]=9;
    G->arc[5][7]=5;
    G->arc[6][7]=2;
    G->arc[6][8]=7;
    
    G->arc[7][8]=4;
    
    
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
    
}

/* 11. 2
 Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。
 Patharc 和 ShortPathTable 都是二维数组;
 */
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
    int v,w,k;
    
    /* 1. 初始化D与P 矩阵*/
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=0; w<G.numVertexes; ++w)
        {
            /* D[v][w]值即为对应点间的权值 */
            (*D)[v][w]=G.arc[v][w];
             /* 初始化P P[v][w] = w*/
            (*P)[v][w]=w;
        }
    }
    
    //2.K表示经过的中转顶点
    for(k=0; k<G.numVertexes; ++k)
    {
        for(v=0; v<G.numVertexes; ++v)
        {
            for(w=0; w<G.numVertexes; ++w)
            {
                /*如果经过下标为k顶点路径比原两点间路径更短 */
                if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
                {
                    /* 将当前两点间权值设为更小的一个 */
                    (*D)[v][w]=(*D)[v][k]+(*D)[k][w];
                    /* 路径设置为经过下标为k的顶点 */
                    (*P)[v][w]=(*P)[v][k];
                }
            }
        }
    }
}

int main(void)
{
    printf("Hello,最短路径弗洛伊德Floyd算法");
    int v,w,k;
    MGraph G;
    
    Patharc P;
    ShortPathTable D; /* 求某点到其余各点的最短路径 */
    
    CreateMGraph(&G);
    
    ShortestPath_Floyd(G,&P,&D);
    
    //打印所有可能的顶点之间的最短路径以及路线值
    printf("各顶点间最短路径如下:\n");
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=v+1; w<G.numVertexes; w++)
        {
            printf("v%d-v%d weight: %d ",v,w,D[v][w]);
            //获得第一个路径顶点下标
            k=P[v][w];
            //打印源点
            printf(" path: %d",v);
            //如果路径顶点下标不是终点
            while(k!=w)
            {
                //打印路径顶点
                printf(" -> %d",k);
                //获得下一个路径顶点下标
                k=P[k][w];
            }
            //打印终点
            printf(" -> %d\n",w);
        }
        printf("\n");
    }
    
    //打印最终变换后的最短路径D数组
    printf("最短路径D数组\n");
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=0; w<G.numVertexes; ++w)
        {
            printf("%d\t",D[v][w]);
        }
        printf("\n");
    }
    //打印最终变换后的最短路径P数组
    printf("最短路径P数组\n");
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=0; w<G.numVertexes; ++w)
        {
            printf("%d ",P[v][w]);
        }
        printf("\n");
    }
    
    return 0;
}

最短路径
最短路径最短路径：http://baike.baidu.com/view/349189.htmDijkstra算...
图的应用-最短路径求解
图的最短路径图的最短路径是一个起点到一个终点之间最短的路径。用于解决最短路径问题的算法被称做“最短路径算...
最短路径之 Bellman 算法
• 最短路径之 Floyd 算法• 最短路径之 Dijkstra 算法 Bellman算法差不多是Floyd算...
Floyd-Warshall 全源最短路径算法
前言全源最短路径是相对单源最短路径而言的，用于查找图中所有点对其它点的最短路径。 Floyd-Warshall算...
据结构与算法学习-最短路径
最短路径顾名思义就是两个点之间所需花费最短的那个路径。在算法中计算最短路径有两个比较著名的算法：Dijkstra算...
最短路径问题概述
【问题概述】最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径．算...
数据结构与算法-最短路径
最短路径定义对于非网图，所谓最短路径是指两顶点之间经过的边数最少的路径；对于网图，是指两顶点之间经过的边上权值和...
codeforces-3A Shortest path of t
题意：在棋盘上给定两点坐标，输出最短到达步数及路径。
5. Floyd算法
Floyd算法：求图中任意一对顶点间的最短路径；通常用方阵来表示图中每两点之间的最短路径的过程方阵的阶数越高...
Java实现广度优先算法-找出图中两个节点的最短路径。
广度优先算法，用来查找图中两个节点的最短路径。这里的最短是指最短边数。思路：从起点开始，依次把自己的邻居放入待搜...