[图](9)最短路径

最短路径

在非网图中,最短路径是指两顶点之间经历的边树最少的路径

在网图中,最短路径是指两顶点之间经历的边上权值之和最短的路径。

假若要在计算机上建立一个交通咨询系统,则可以采用图的结构来表示实际的交通网络,如下图所示,

image-20210130134439527

图中顶点表示城市,边表示城市间的交通联系,这个咨询系统可以回答,旅客提出的各种问题,例如:

  • 一位旅客要从A城到B城,他希望选择一条途中中转次数最少的路线,假设图中每一站都需要换车,则这个问题反映到图上就是要找一条从顶点A到B所含边的数目最少的路径
  • 我们需要从顶点A出发对图作广度优先搜索,一旦遇到顶点B就终止,由此所得广度优先生成树上,从根顶点A到顶点B的路径就是中转次数最少的路径,路径上A与B之间的顶点就是途径的中转站数,但是,这只是一类最简单的图的最短路径问题
  • 有时,对于旅客来说,可能更为关心的是节省交通费用,而对于司机来说,里程和速度则是他们感兴趣的信息,为了在图上表示有关信息,可对边赋以权,权的值表示两城市间的距离,或途中所需时间,或交通费用等等
  • 此时路径长度的度量就不再是路径上边的数目,而是路径上边的权值之和,考虑到交通图的有向性(如航运,逆水和顺水时的船速就不一样)
  • 我们主要讨论带权的有向图,并称路径上的第一个顶点为源点(Sourse),最后一个顶点为终点(Destination)。下面讨论两种最常见的最短路径问题
交通网络用有向图表示:
  • 顶点表示地点
  • 弧表示两个地点有路相同
  • 弧上的权值表示两地点之间的距离,交通费或途中所花费的时间等

可把上述问题抽象为:在有向网中从A点(源点)到达B点(终点)的多条路径,寻找一条各边权值之和最小的路径,即为最短路径

最短路径与最小生成树不同,路径上不一定包含N个顶点,也不一定包含n-1条边

主要问题点

第一类问题:两点间最短路径(所有顶点间的最短路径)

第二类问题:某源点到其他各点最短路径(从一个顶点到另一个顶点的最短路径)

从某个源点到其余各顶点的最短路径

我们先来讨论单源点的最短路径问题:给定带权有向图G和源点v,求从v到G中其余个顶点的最短路径。

例如:下图所示带权有向图G中从V0到其余各顶点之间的最短路径,从右图可见,从V0到V3有两条不同的路径:(V0,V2,V3)和(V0,V4,V3),前者长度为60,而后者长度为50,因此,后者是从V0到V3的最短路径,而从V0到V1没有路径

请输入图片描述

迪杰斯特拉(Dijkstra)算法

如何求得这些路径?迪杰斯特拉(Dijkstra)提出了一个按路径长度递增的次序产生最短路径的算法:

基本思想:

  • 设置一个集合S存放已经找到最短路径的顶点,S的初始状态只包含源点v
  • 初始化:先找出源点v0到各终点vk的直达路径(v0,vk)

    • 即通过一条弧到达的路径
  • 选择:从这些路径中找出一条长度最短的路径(v0,u)
  • 更新:然后对其余各条路径进行适当调整

    • 若图中存在弧(u,vk),且(v0,u)+(u,vk)<(v0,vk)
    • 则以路径(v0,u,vk)代替(v0,vk)

在调整后各路径中,再找出长度最短的路径,重复上述过程

  • 数据结构:带权的邻接矩阵存储结构(需要多次查询弧的权值)
  • 数组dist[n]:每个分量dist[i]表示当前所找到的从始点v到达终点vi的最短路径长度,初态为:若从v到vi有弧,则dist[i]为弧上的权值,否则置dist[i]为∞
  • 数组path[n]:表示当前找到的从始点v到终点vi的最短路径,初态为:若从v到vi有弧,则path[i]为i,否则置path[i]为-1
  • 数组s[n]:存放源点和已经生成的终点,其初态为只有一个源点v

Dijkstra算法伪代码

 1、初始化数组dist、path和s
 2、while(s中的元素个数<n)
   2.1、在dist[n]中求最小值,其下标为k
   2.2、输出dist[j]和path[j]
   2.3、修改数组dist和path
   2.4、将顶点vk添加到数组s中

图解:

请输入图片描述

以上图G4为例

请输入图片描述

算法如下所示:

int FindMinArc(int *dist, int* s,int nums) {
    int min = INFINITY;
    int index = -1;
    for (int i = 0; i < nums; i++) {
        if (s[i] != 1 && min > dist[i]) {
            min = dist[i];
            index = i;
        }
    }
    return index;
}

void PrintPathing(int* path, int start, int i) {
    if (path[i] == start) {
        printf("%d ", path[i]);
        return;
    }
    PrintPathing(path, start,path[i]);
    printf("%d ", path[i]);
    return;
}

void displayPath(int* dist, int* path, MGraph G, int start) {
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vexs[i] == start) continue;
        printf("V(%d)-->v(%d) 's Min path :  ", start, G.vexs[i]);
        int j = G.vexs[i];
        PrintPathing(path, start, j);//使用递归反向输出
        printf("%d ", i);
        printf("\n");
    }
    return;
}
Status Dijkstra(MGraph* G, VRType start) {
    if (start >= G->vexnum) return ERROR;//给定结点序号越界
    //分配三个数组

    /*
    数组dist[n]:每个分量dist[i]表示当前所找到的从始点v到达终点vi的最短路径长度
                 初态为:若从v到vi有弧,则dist[i]为弧上的权值,否则置dist[i]为∞
    数组path[n]:表示当前找到的从始点v到终点vi的最短路径
                 初态为:若从v到vi有弧,则path[i]为0,否则置path[i]为-1
    数组s[n]:存放源点和已经生成的终点,其初态为只有一个源点v
    */
    int* dist = (int*)malloc(sizeof(int) * G->vexnum);
    int* s = (int*)malloc(sizeof(int) * G->vexnum);
    int* path = (int*)malloc(sizeof(int) * G->vexnum);
    for (int i = 0; i < G->vexnum; i++) {
        s[i] = 0;//初始化集合S,初始化为0
        if (G->arcs[start][i].adj != INFINITY) path[i] = start;
        else path[i] = -1;//初始化path
        dist[i] = G->arcs[start][i].adj;//初始化dist
    }
    s[start] = 1;//顶点放入集合S,1代表在集合中,0代表不在集合中
    int num = 1;
    while (num < G->vexnum) {//当顶点数num小于图的顶点数
        int min = FindMinArc(dist, s, G->vexnum);//dist中查找s[i]为0的最小元素值(找寻其当前最小代价边)
        s[min] = 1;//将新生成的终点加入集合S
        if (min == -1) return ERROR;
        for (int i = 0; i < G->vexnum; i++) {
            if (s[i] == 0 && G->arcs[min][i].adj != INFINITY && G->arcs[min][i].adj + dist[min] < dist[i]) {
                /*
                for (int i = 0; i < G->vexnum; i++) printf("%d ", s[i]);
                system("pause");
                */
                path[i] = min;//用已经找到的最短路径修改对应的dist
                dist[i] = G->arcs[min][i].adj + dist[min];//用已经找到的最短路径修改对应的path
            }
        }
        num++;
    }

    displayPath(dist, path, *G, start);//打印起始点到终点的    最短路径
    return OK;
}

算法演示如懒猫老师讲解。

所有顶点间的最短路径

方法一:每次以一个顶点为源点,重复执行dijkstra算法n次

方法二:弗洛伊德(Floyd)算法

弗洛伊德(Floyd)算法

算法思想:

弗洛伊德算法仍从带权邻接矩阵cost出发,其基本思想是:

  • 对于从v(i)到v(j)的弧,进行n次试探:首先考虑路径v(i),v(k),v(j)是否存在,如果存在,则比较v(i),v(j)和v(i),v(k),v(j)的路径长度,取较短者为从v(i)到v(j)的中间路径
  • 在路径上再增加一个顶点,以此类推,在经过n次比较后,最后求得的必是从顶点vi到vj的最短路径

从上可以得知这是一个动态规划的思想,其准备工作如下所示:

  • 图的存储结构:带权的邻接矩阵存储结构
  • 数组distn:存放迭代过程中求得的最短路径长度,其状态转移方程如下所示:

    • 初始状态:disti=arci
    • 整体情况:dist(k)i=min{dist(k-1)i,dist(k-1)i+dist(k-1)k}
  • 数组pathn:存放从vi到vj的最短路径,初始化为pathi=“vi,vj”

    • 迭代进行顶点的拼接

但看上面可能很难理解,下面给出图示:

请输入图片描述

以上图G4为例,来对弗洛伊德进行算法演示。

请输入图片描述

初始状态:dist是记录各个顶点间最短路径的矩阵。
第1步:初始化dist。
矩阵dist中顶点ai的距离为顶点i到顶点j的权值;如果i和j不相邻,则ai=∞。实际上,就是将图的原始矩阵复制到dist中。
注:ai表示矩阵中顶点i(第i个顶点)到顶点j(第j个顶点)的距离。

第2步:以顶点A(第1个顶点)为中介点,若ai > ai+a0,则设置ai=ai+a0。
以顶点a[1]6,上一步操作之后,a1=∞;而将A作为中介点时,(B,A)=12,(A,G)=14,因此B和G之间的距离可以更新为26。

同理,依次将顶点B,C,D,E,F,G作为中介点,并更新ai的大小。

算法如下所示:

//数据结构:
/*
typedef int VerTexType;
typedef int VRType;
typedef int InfoType;

typedef struct ArcCell {
    VRType adj;//顶点类型
    InfoType info;//顶点附加信息
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {
    VerTexType vexs[MAX_VERTEX_NUM];//顶点表
    AdjMatrix arcs;//邻接矩阵
    int vexnum, arcnum;//顶点数和边数
    GraphKind kind;//顶点类型
}MGraph;
*/

//利用递归反向输出路径,采用树的双亲表思路
void PrintPathing(int* path, int start, int i) {
    if (path[i] == start) {
        printf("%d ", path[i]);
        return;
    }
    PrintPathing(path, start,path[i]);
    printf("%d ", path[i]);
    return;
}
Status Floyd(MGraph* G) {
    //初始化矩阵path和dist
    int** dist = (int**)malloc(sizeof(int*) * G->vexnum);
    int** path = (int**)malloc(sizeof(int*) * G->vexnum);
    
    for (int i = 0; i < G->vexnum; i++) {
        dist[i] = (int*)malloc(sizeof(int) * G->vexnum);
        path[i] = (int*)malloc(sizeof(int) * G->vexnum);
        for (int j = 0; j < G->vexnum; j++) {
            dist[i][j] = G->arcs[i][j].adj;
            if (dist[i][j] == INFINITY) path[i][j] = -1;
            else path[i][j] = i;
        }
    }
    
    //开始状态更新
    for (int k = 0; k < G->vexnum; k++) {//中间点
        for (int i = 0; i < G->vexnum; i++) {//起点
            for (int j = 0; j < G->vexnum; j++) {//终点
                if (i == j || i == k || k == j) continue;
                if (dist[i][k] + dist[k][j] < dist[i][j]) {//若从起点到中间的的耗费加上从中间点到终点的耗费小于上一从起点到终点的耗费
                    dist[i][j] = dist[i][k] + dist[k][j];//则将当前起点到终点的耗费更新
                    path[i][j] = path[k][j];//同时当前从起点的终点的路径要更新为从中间点到终点的路径
                }
            }
        }
    }
    //打印路径
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            printf("V(%d)-->V(%d) is min path:", i, j);
            if (path[i][j] == -1) {
                printf("No Path");
            }
            else {
                PrintPathing(path[i], i, j);
                printf("%d", j);
            }
            printf("\n");
        }
        printf("\n");
    }
    system("pause");
    return OK;
}

测试数据:

请输入图片描述

请输入图片描述

测试文本:

7,12
0
1
2
3
4
5
6
0,1,4
0,2,6
0,3,6
1,2,1
1,4,7
2,4,6
2,5,4
3,2,2
3,5,5
5,4,1
5,6,8
4,6,6

本文链接:

https://nullcode.fun/132.html
1 + 8 =
快来做第一个评论的人吧~