数据结构与算法(十三)：图的应用-最短路径-Dijkstra/F

作者: 顶级蜗牛 | 来源:发表于2023-11-23 16:27 被阅读0次

数据结构与算法--最短路径之Floyd算法
《算法》笔记 12 - 最短路径
21-Bellman-Ford算法
7.8图的应用：最短路径问题
图
最短路径之 Dijkstra 算法
迪杰斯特拉（Dijkstra）算法
最短路径之 Bellman 算法
2018-07-22
（转）Dijkstra 最短路径算法秒懂详解

一、最短路径

当你从一个城市去到另一个城市，可以选择中间跨越不同的地方，选择不一样的路径，最终到达终点。

最短路径就是从起点到达终点怎么走是最短的，但是会面临两种情况：1.带权值的网图；2.不带权值的连通图。

1.带权值的网图：从起点到终点所累积的权值总和最小（权值可理解成路程）；
2.不带权值的连通图：从起点到终点的边数总和最小。

举例网图：

带权值的网图

要从V0出发到V8

最短路径: V0 — V1 — V2 — V4 — V3 —V6 —V7 — V8
最短路径权值和: 1 + 3 + 1 + 2 +3 + 2 + 4 = 16

二、最短路径 - 迪迦斯特(Dijkstra)算法

带权值的网图

用邻接矩阵存储网图

邻接矩阵存储网图

1.算法分析

定义三个数组去记录

从0开始：

//V0到V0是没有路径的.
final[v0] = 1; 
//V0到V0的路径为0
(*D)[v0] = 0;
//V0到V0是没有路径的.所以-1;
(*P)[v0] = -1;

final数组：表示V0 到某个顶点 Vw 是否已经求得了最短路径的标记；
如果V0 到 Vw 已经有结果，则final[w] = 1。（避免往回走的情况）

D数组：表示V0 到某些顶点的路径，∞表示暂时还不能直接到达；
此时的数据是此时是V0所能到达顶点。

现在D数组是V0到其它顶点的直接路径，但是我们代码回去修改数组的数据，变成间接路径。

p数组：存储当前顶点的前驱顶点的下标。-1表示V0出发还没有前驱。

第1次执⾏：看找到V1是怎么记录的

V0->V1的权值 = 1
V0->V2的权值 = 5

在D数组中V1的权值更小(1<5，0不考虑是因为final标记过为1)，所以min=1 (min记录上一次边权值)。

final数组:
V0->V1存在最短路径 final[1] = 1 标记好防止往回找。

此时V1能直接到的地方：V0、V2、V3、V4，由于V0在final数组中已经标记过了不能回流，所以此时只剩下V2、V3、V4

D数组：
V0->V1->V2的权值 = min+3 = 4 < 5，此刻D[2] = 4代替掉原本的5；
V0->V1->V3的权值 = min+7 = 8 < ∞，此刻D[3] = 8代替掉原本的∞；
V0->V1->V4的权值 = min+5 = 6 < ∞，此刻D[4] = 6代替掉原本的∞。

p数组：

p数组记录V2、V3、V4的前驱顶点是V1。

第2次执⾏：看找到V2是怎么记录的

看D数组中的数据：
V0->V1->V2的权值 = 4
V0->V1->V3的权值 = 8
V0->V1->V4的权值 = 6

在D数组中V2的权值更小(4<6<8)，所以min=4 (min记录上一次边权值)。

final数组:
在V0->V1->V2存在最短路径 final[2] = 1 标记好防止往回找。

此时V2能直接到的地方：V0、V1、V4、V5，由于V0/V1在final数组中已经标记过了不能回流，所以此时只剩下V4、V5。

D数组：
V0->V1->V2->V4的权值 = min+1 = 5 < 6，此刻D[4] = 5代替掉原本的6；
V0->V1->V2->V5的权值 = min+7 = 11 < ∞，此刻D[5] = 11代替掉原本的∞；

p数组：

p数组记录V4、V5的前驱顶点是V2。

第3次执⾏：看找到V4是怎么记录的

看D数组中的数据：
由于final标记了V0、V1、V2存在最短路径，无需看在D数组中的V0、V1、V2：
V0->V1->V3的权值 = 8
V0->V1->V2->V4的权值 = 5
V0->V1->V2->V5的权值 = 11

在D数组中V4的权值更小(5<8<11)，所以min=5 (min记录上一次边权值)。

final数组:
在V0->V1->V2->V4存在最短路径 final[4] = 1 标记好防止往回找。

此时V2能直接到的地方：V1、V2、V3、V5、V6、V7，由于V1/V2在final数组中已经标记过了不能回流，所以此时只剩下V3、V5、V6、V7。

D数组：
V0->V1->V2->V4->V3的权值 = min+2 = 7 < 8，此刻D[3] = 7代替掉原本的8；
V0->V1->V2->V4->V5的权值 = min+3 = 8 < 11，此刻D[5] = 8代替掉原本的11；
V0->V1->V2->V4->V6的权值 = min+6 = 11 < ∞，此刻D[6] = 11代替掉原本的∞；
V0->V1->V2->V4->V7的权值 = min+9 = 14 < ∞，此刻D[7] = 14代替掉原本的∞。

p数组：

p数组记录V3、V5、V6、V7的前驱顶点是V4。

第4次执⾏：看找到V3是怎么记录的

看D数组中的数据：
由于final标记了V0、V1、V2、V4存在最短路径，无需看在D数组中的V0、V1、V2、V4：
V0->V1->V2->V4->V3的权值 = 7
V0->V1->V2->V4->V5的权值 = 8
V0->V1->V2->V4->V6的权值 = 11
V0->V1->V2->V4->V7的权值 = 14

在D数组中V4的权值更小(7<8<11<14)，所以min=7 (min记录上一次边权值)。

final数组:
在V0->V1->V2->V4->V3存在最短路径 final[3] = 1 标记好防止往回找。

此时V3能直接到的地方：V1、V4、V6，由于V1/V4在final数组中已经标记过了不能回流，所以此时只剩下V6。

D数组：
V0->V1->V2->V4->V3->V6的权值 = min+3 = 10 <11，此刻D[6] = 10代替掉原本的11。

p数组：

p数组记录V6的前驱顶点是V3。

第5次执⾏：看找到V6后，为啥去找V5->V7

看D数组中的数据：
由于final标记了V0、V1、V3、V2、V4存在最短路径，无需看在D数组中的V0、V1、V3、V2、V4：
V0->V1->V2->V4->V5的权值 = 8
V0->V1->V2->V4->V3->V6的权值 = 10
V0->V1->V2->V4->V7的权值 = 14

在D数组中V4的权值更小(8<10<14)，所以min=8 (min记录上一次边权值)。

final数组:
在V0->V1->V2->V4->V5存在最短路径 final[5] = 1 标记好防止往回找。

此时V4能直接到的地方：只剩下V5、V6、V7（因为其它位已被final标记）。

D数组：
V0->V1->V2->V4->V5的权值 = min+3 = 11 > 8，此刻D[5]依旧为8；
V0->V1->V2->V4->V6的权值 = min+6 = 14 <10，此刻D[6]依旧为10；
V0->V1->V2->V4->V7的权值 = min+9 = 17 <14，此刻D[7] 依旧为14；
V0->V1->V2->V4->V5->V7的权值 = min+5 = 13 < 14,此刻D[7] = 13代替掉原本的14。

p数组：

p数组记录V7的前驱顶点是V5。

第6次执⾏：权衡V5/V6，决定V6->V7

看D数组中的数据：
由于final标记了V0、V1、V2、V3、V4、V5存在最短路径，无需看在D数组中的V0、V1、V2、V3、V4、V5：
V0->V1->V2->V4->V3->V6的权值 = 10
V0->V1->V2->V4->V5->V7的权值 = 13

在D数组中V6的权值更小(0<13)，所以min=10 (min记录上一次边权值)。

final数组:
在V0->V1->V2->V4->V3->V6存在最短路径 final[6] = 1 标记好防止往回找。

此时V6能直接到的地方：只剩下V7、V8（因为V3/V4已被final标记）。

D数组：
V0->V1->V2->V4->V3->V6->V7的权值 = min+2 = 12 < 13，此刻D[7] = 12代替掉原本的13;
V0->V1->V2->V4->V6->V8的权值 = min+7 = 17 < ∞，此刻D[8] = 17代替掉原本的∞。

p数组：

p数组记录V7、V8的前驱顶点是V6。

第7次执⾏：权衡V6/V7，决定V7->V8

看D数组中的数据：
由于final标记了V0、V1、V2、V3、V4、V5、V6存在最短路径，无需看在D数组中的V0、V1、V2、V3、V4、V5、V6：
V0->V1->V2->V4->V3->V6->V7的权值 = 12
V0->V1->V2->V4->V3->V6->V8的权值 = 17

在D数组中V6的权值更小(12<17)，所以min=12 (min记录上一次边权值)。

final数组:
在V0->V1->V2->V4->V3->V6->V7存在最短路径 final[7] = 1 标记好防止往回找。

此时V7能直接到的地方：只剩下V8。

D数组：
V0->V1->V2->V4->V3->V6->V7->V8的权值 = min+4 = 16 < 17，此刻D[7] = 16代替掉原本的17。

p数组：

p数组记录V8的前驱顶点是V7。

第8次执⾏：确定V8的路径

由于此时final数组里只有V8没有被标记，所以min=16 == 16

final数组:
在V0->V1->V2->V4->V3->V6->V7->V8存在最短路径 final[8] = 1。

D数组、p数组都不变

此时D数组存储的就是V0到每一个顶点的最短路径的权值之和；
此时p数组存储的就是V0出发，每一个顶点的前驱。

2.算法实现

通过邻接矩阵创建图

#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#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];
        }
    }
    
}

Dijkstra算法实现

/*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)算法

1.简化推演公式

求 V1->V2 最短路径?

有 V1->V2 = 5 或者 V1->V0->V2 = 3 两种路径；
该图的邻接矩阵就可以有下面这样的演变：

D数组存储最短路径权值

P数组存储前驱节点

于是推演出该公式：

2.算法执行过程分析

带权值的网图

得到初始化的两个临街矩阵 D和P：

/* 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;
   }
 }

初始化两个邻接矩阵 D和P

最短路径的遍历：

//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];
      }
    }
  }
}

根据公式去推导

第1次执⾏：
当 K = 0 时, 也就是所有顶点都经过V0中转, 计算是否有最短路径的变化。所以k=0时，D和P没有发⽣任何变换。
第2次执⾏：
当 K = 1 时, 也就是所有顶点都经过V1 中转

D矩阵的变化

P矩阵的变化

（下面就不画图了，直接给执行过程，并不完全，只是给个套上公式后的推导）

这里只分析到K=1的情况，下面还有好多好多....
该算法时间复杂度是 8³。

最终得到的D和P的存储数据如下：

最终数据D和P

D矩阵存放了每一个顶点到任意一个顶点的最短路径，比如V2->V8是12；
以V2->V8来看，P矩阵应该这样看：
V2->V8 经历过V4 （P[2][8]）
V2->V4->V8 经历过V3 （P[4][8]）
V2->V4->V3->V8 经历过V6 （P[3][8]）
V2->V4->V3->V6->V8 经历过V7 （P[6][8]）
V2->V4->V3->V6->V7->V8 经历过V8 （P[7][8]）
V2->V4->V3->V6->V7->V8才是最终的路径（P[8][8]）

3. 算法实现

初始化图

#include <stdio.h>
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#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];
        }
    }
    
}

Floyd算法

/* 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;
}

数据结构与算法--最短路径之Floyd算法
数据结构与算法--最短路径之Floyd算法我们知道Dijkstra算法只能解决单源最短路径问题，且要求边上的权重...
《算法》笔记 12 - 最短路径
加权有向图数据结构加权有向边加权有向图最短路径边的松弛 Dijkstra算法地图或者导航系统是最短路径的典型...
21-Bellman-Ford算法
在前面，介绍了Dijkstra算法，计算图的最短路径，但是Dijkstra算法在计算最短路径时，有一个前提，就是不...
7.8图的应用：最短路径问题
最短路径问题：Dijkstra算法 ❖解决带权最短路径问题的经典算法是以发明者命名的“Dijkstra算法”❖这是...
图
遍历最短路径 1.单源最短路有权图-Dijkstra 多源头最短路-Floyd算法 —————————————...
最短路径之 Dijkstra 算法
• 最短路径之 Floyd 算法• 最短路径之 Bellman 算法 Dijkstra算法是用于求解单源最短路...
迪杰斯特拉（Dijkstra）算法
Dijkstra是著名的图算法 Dijkstra算法解决有权图从【一个节点到其他节点的最短路径问题】以起始点为中...
最短路径之 Bellman 算法
• 最短路径之 Floyd 算法• 最短路径之 Dijkstra 算法 Bellman算法差不多是Floyd算...
2018-07-22
最短路径算法之Dijkstra算法基本思想通过Dijstra计算图G中的最短路径时，需要指定起点s（即从顶点s...
（转）Dijkstra 最短路径算法秒懂详解
Dijkstra 最短路径算法秒懂详解