数据结构（22）图的最短路径

旧城等待， 2022-12-10 01:29 140阅读 0赞

### 数据结构（22）图的最短路径 ###

*   *   *  前言
         *  迪杰斯特拉算法
         *  全部代码
         *   *  Main.c
             *  GraphMtx.h
             *  GraphMtx.c
         *  后记

### 前言 ###

本篇是数据结构系列的最后一篇了，当然，涉及到数据结构还有一些排序算法、搜索算法没有写出来，以后会慢慢补上。

我们说的最短路径，指的是从有向图中，某一顶点A到另一顶点B的最短路径。

这就有两种情况：第一种是不考虑边的权值，而考虑中转次数，求的是A到B最少需要经过几条边。第二种则是考虑边的权值，求从A到B路径上权值之和最短的一条。

如图所示，从A到E的路径有：A-E（100），A-D-C-E（60），A-D-E（90），A-B-C-E（70）等等。假如是第一种情况，需要找到的是A-E边，而第二种情况，需要找到的是A-D-C-E边。

![img\_1][img_1]

这里我们说的最短路径是第二种情况，所实现的算法为迪杰斯特拉算法。

### 迪杰斯特拉算法 ###

迪杰斯特拉算法的思路是：

1.  从要寻找的起点A开始，维护一个记录到达其他顶点X最短距离的数组dist，若不可达，则存为MAX\_VALUE。
2.  将**数组中**拥有最短距离的顶点B纳入A顶点集合，然后去统计 **从B到其余顶点X的距离，加上A到B的距离**，是否小于之前要到达X的最短距离，若小于，则更新最短距离数组。
    
    注：最短距离数组中存放的可能是A直达X的距离，也可能是A到C，C再到X的距离。总之存储的是当前情况下A到X的最短距离。
3.  重复第二步，直到找完最后一个顶点为止。

很显然，当一个顶点被纳入A顶点集合之后，是不会再重复纳入的。这就要求我们再维护一个visited数组，记录当前顶点是否已经被纳入集合。同时，还需要一个path数组记录到达每一个顶点的路径。

直接看例子：

![img\_2][img_2]

1.  求从A出发到达各个顶点的最短路径，此时初始化数组，dist数组中记录的是A到其余顶点边的权值，若无边，则为最大值（表示不可达）。path数组记录了A到达各个顶点的路径，A无法到达自己，记录为-1，C不可达，记录为最大值。而visited数组记录了已经纳入A集合的顶点，此时只有A。
2.  从dist数组中找到最短距离的顶点，此时为B，将B纳入A顶点集合（visited\[1\] = 1)。统计从B到其余顶点的距离，加上A-B的距离10，是否小于dist数组中存储的距离。可以发现，A-B-C为60，小于原来的A-C的最大值，更新dist数组。并且将到达C的路径改为B的下标(path\[2\] = 1)。
    
    注：path记录了A到其余顶点的路径。path\[2\] 值为 1，意味着要到达C，首先要到达B（path\[1\]），而要到达C，首先要到达path\[0\]，path\[0\] 值为 -1，说明就是从path\[0\]出发的，这样就可以找到A-B-C的路径。
3.  从dist数组中找到最短距离的顶点，此时为D，将D纳入A顶点集合（visited\[3\] = 1）。统计从D到其余顶点的距离，加上A-D的距离30，是否小于dist数组中存储的距离。可以发现，A-D-E为90，小于原来A-E的最大值；A-D-C为50，也小于原来的A-B-C最大值，更新dist数组。并且修改到达E、C的路径为D的下标。

![img\_3][img_3]

1.  从dist数组中找到最短距离的顶点，此时为C，将C纳入A顶点集合（visited\[2\] = 1）。统计从C到其余顶点的距离，加上A-C的距离50，是否小于dist数组中存储的距离。可以发现，A-D-C-E为60，小于原来A-D-E的最大值，更新dist数组。并且修改到达E的路径为C的下标。
2.  从dist数组中找到最短距离的顶点，此时为E，将E纳入A顶点集合（visited\[4\] = 1）。统计从E到其余顶点的距离，加上A-E的距离60，是否小于dist数组中存储的距离。此时无可更新的数据。

当整个迪杰斯特拉算法运行结束后，我们就可以得到A到达每一个顶点的最短距离dist\[\]，和路径path\[\]。

### 全部代码 ###

#### Main.c ####

#include "GraphMtx.h"
    
    int main(int argc, const char * argv[]) { 
        GraphMtx gm;
        InitGraph(&gm);
        InsertVertex(&gm,'A');
        InsertVertex(&gm,'B');
        InsertVertex(&gm,'C');
        InsertVertex(&gm,'D');
        InsertVertex(&gm,'E');
     
        InsertEdge(&gm,'A','B',10);
        InsertEdge(&gm,'A','D',30);
        InsertEdge(&gm,'A','E',100);
        InsertEdge(&gm,'B','C',50);
        InsertEdge(&gm,'C','E',10);
        InsertEdge(&gm,'D','C',20);
        InsertEdge(&gm,'D','E',60);
        ShowGraph(&gm);
        
        
        int n = gm.NumVertices;
        int *dist = (int *)malloc(sizeof(int) * n);
        int *path = (int *)malloc(sizeof(int) * n);
        assert(dist != NULL && path != NULL);
        
        ShortestPath(&gm,'A',dist,path);
        for (int i = 0; i < n; i ++) { 
            printf("%d ",path[i]);
        }
        printf("\n");
        for (int i = 0; i < n; i ++) { 
            printf("%d ",dist[i]);
        }
        printf("\n");
        DestoryGraph(&gm);
        
        return 0;
    }

#### GraphMtx.h ####

#ifndef GraphMtx_h
    #define GraphMtx_h
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    //默认的顶点个数
    #define DEFAULT_VERTEX_SIZE 10
    //初始化的距离
    #define DEFAULT_MAX_COST 0x7FFFFFF
    //顶点的数据类型
    #define T char
    
    //边结构
    typedef struct Edge{ 
        //边的起点
        int x;
        //边的终点
        int y;
        //边的权值
        int cost;
    }Edge;
    
    typedef struct GraphMtx{ 
        //最大的顶点数
        int MaxVertices;
        //现有的顶点数
        int NumVertices;
        //现有的边数
        int NumEdges;
        
        //顶点列表
        T *VerticesList;
        //边->矩阵
        int **Edge;
    }GraphMtx;
    
    //初始化
    void InitGraph(GraphMtx *g);
    
    //展示图
    void ShowGraph(GraphMtx *g);
    
    //获取顶点位置
    int GetVertexPos(GraphMtx *g,T v);
    
    //插入顶点
    void InsertVertex(GraphMtx *g,T v);
    //插入边-无向
    void InsertEdge(GraphMtx *g,T v1,T v2,int cost);
    
    //摧毁图
    void DestoryGraph(GraphMtx *g);
    
    //获取权值
    int GetWeight(GraphMtx *g, int v1, int v2);
    //狄杰斯提拉算法
    void ShortestPath(GraphMtx *g,T vertex,int *dist,int *path);
    #endif /* GraphMtx_h */

#### GraphMtx.c ####

#include "GraphMtx.h"
    
    //初始化
    void InitGraph(GraphMtx *g){ 
        //数据初始化
        g->MaxVertices = DEFAULT_VERTEX_SIZE;
        g->NumVertices = g->NumEdges = 0;
        
        //开辟储存顶点的空间
        g->VerticesList = (T*)malloc(sizeof(T) * g->MaxVertices);
        assert(g->VerticesList != NULL);
        
        //开辟储存边的空间
        g->Edge = (int **)malloc(sizeof(int*) * g->MaxVertices);
        assert(g->Edge != NULL);
        for (int i = 0; i < g->MaxVertices; i ++) { 
            g->Edge[i] = (int *)malloc(sizeof(int) * g->MaxVertices);
            assert(g->Edge[i] != NULL);
        }
        
        //初始化边
        for (int i = 0; i < g->MaxVertices; i ++) { 
            for (int j = 0; j < g->MaxVertices; j ++) { 
                if (i == j) { 
                    g->Edge[i][j] = 0;
                }else{ 
                    g->Edge[i][j] = DEFAULT_MAX_COST;
                }
            }
        }
    }
    
    //展示图
    void ShowGraph(GraphMtx *g){ 
        
        //打印第一排的顶点
        printf(" ");
        for (int i = 0; i < g->NumVertices; i ++) { 
            printf(" %3c",g->VerticesList[i]);
        }
        printf("\n");
        
        //打印边->矩阵
        for (int i = 0; i < g->NumVertices; i ++) { 
            printf("%c",g->VerticesList[i]);
            for (int j = 0; j < g->NumVertices; j ++) { 
                if (g->Edge[i][j] == DEFAULT_MAX_COST) { 
                    printf("%4s","@");
                }else{ 
                    printf("%4d",g->Edge[i][j]);
                }
            }
            printf("\n");
        }
        printf("\n");
    }
    
    //获取顶点位置
    int GetVertexPos(GraphMtx *g,T v){ 
        for (int i = 0; i < g->NumVertices; i ++) { 
            if (g->VerticesList[i] == v) { 
                return i;
            }
        }
        return -1;
    }
    
    //插入顶点
    void InsertVertex(GraphMtx *g,T v){ 
        if (g->NumVertices == g->MaxVertices) { 
            printf("顶点已满，无法插入\n");
            return;
        }
        g->VerticesList[g->NumVertices ++] = v;
    }
    //插入边
    void InsertEdge(GraphMtx *g,T v1,T v2,int cost){ 
        //获取v1的位置
        int p1 = GetVertexPos(g, v1);
        //获取v2的位置
        int p2 = GetVertexPos(g, v2);
        if (p1 == -1 || p2 == -1) { 
            printf("有顶点不存在\n");
            return;
        }
        
        g->Edge[p1][p2] = cost;
        g->NumEdges ++;
        
    }
    
    //摧毁图
    void DestoryGraph(GraphMtx *g){ 
        //释放顶点空间
        free(g->VerticesList);
        g->VerticesList = NULL;
        for (int i = 0; i < g->NumVertices; i ++) { 
            free(g->Edge[i]);
        }
        g->Edge = NULL;
        g->MaxVertices = g->NumEdges = g->NumVertices = 0;
    }
    
    int GetWeight(GraphMtx *g, int v1, int v2){ 
        return (v1 == -1 || v2 == -1) ? DEFAULT_MAX_COST : g->Edge[v1][v2];
    }
    
    //狄杰斯提拉算法
    void ShortestPath(GraphMtx *g,T vertex,int *dist,int *path){ 
        int n = g->NumVertices;
        int *s = (int *)malloc(sizeof(int) * n);
        assert(s != NULL);
        
        //初始化数据
        //要出发的顶点即V顶点
        int v = GetVertexPos(g, vertex);
        for (int i = 0; i < n; i ++) { 
            //获取到每个顶点到V的距离
            dist[i] = GetWeight(g, v, i);
            //该顶点还没有被访问到
            s[i] = 0;
            
            if (i != v && dist[i] < DEFAULT_MAX_COST) { 
                //距离小于最大距离->说明有从V直接到该顶点的路径
                path[i] = v;
            }else{ 
                //v自己到自己的路径为-1
                path[i] = -1;
            }
        }
        
        //初始顶点已经访问完了->将初始顶点加入集合
        s[v] = 1;
        
        //从当前可达的路径中，找到最短的一条，加入集合
        int min;
        int w;
        for (int i = 0; i < n-1; i ++) { 
            min = DEFAULT_MAX_COST;
            //记录当前最短路径顶点的下标
            int u = v;
            //找到当前最小的一条路径
            for (int j = 0; j < n; j ++) { 
                if (s[j] == 0 && dist[j] < min) { 
                    //当前顶点未被访问到，且小于最短路径->更新最短路径
                    u = j;
                    min = dist[j];
                }
            }
            
            //将该顶点纳入集合
            s[u] = 1;
            //更新该顶点纳入集合后的路径信息
            for (int k = 0; k < n; k ++) { 
                //从该顶点出发，到每个顶点k的距离
                w = GetWeight(g, u, k);
                if (!s[k] && w < DEFAULT_MAX_COST && (dist[u]+w) <
                    dist[k]) { 
                    //k顶点未被访问过，且从u到k有路径，并且从u到k的距离，加上起始点到u的距离之和 小于之前存储的到k的距离->更新信息
                    //从起始点到k的路径等于 从起始点到u的路径加上从u到k的路径
                    dist[k] = dist[u] + w;
                    //到达k的起始点改为u
                    path[k] = u;
                }
            }
            
        }
    }

### 后记 ###

这篇博客写完了，不知道为啥一直没发出去，整理资料的时候才发现……

数据结构系列的博客，多是记录我学习、动手的一个过程，因此对于其他人来说，可读性不会特别好。今后的博客，我更希望从分享的角度出发，把所掌握的知识总结出来，能让更多人看懂、有收获。这就要求我要有足够的知识深度与广度，也算是对自己的一种挑战吧，冲鸭。

[img_1]: /images/20221123/a3a5a64ace524c77b6c15cfaed0b6b6d.png
[img_2]: /images/20221123/f53464546fc948528c0c61c3635aa8a3.png
[img_3]: /images/20221123/68188e53132b4e0696ec5bf1258a5871.png