图的应用——迪杰斯特拉最短路径

灰太狼 2021-11-16 15:20 312阅读 0赞

**采用广度优先搜索思想，对有向赋权图寻找最短路径。  
该算法对于不含负权的有向图来说，是目前已知的最快的单源最短路径算法。  
时间复杂度：O（n^2）**  
**基本原理：不断为为每个顶点 v 保留目前为止所找到的从s到v的最短路径**  
![示意图][SouthEast]  
上图为迪杰斯特拉算法应用示意图。  
起点以左下角的**红点**，目标是右上角的**绿点**，中间灰色的倒L型为障碍物。蓝色空圈表示”暂定”，用以搜索下一步；已经填充颜色的表示探访过，图中颜色以红到绿，越绿表示离起点越远。所有节点都被均匀的探索。

我们以下图为例：  
![有向赋权图][SouthEast 1]  
假设以“1”为顶点出发，求解到每个顶点的最短路径，若可达，则输出最短路径；若不可达，则输出无穷大（32767）

shortest(1, 2)=2  
![1，2][1_2]  
shortest(1, 3)=4  
![1，3][1_3]  
shortest(1, 4)=5  
注：经对比，第二种路径得到的权值和较小，取第二种方式  
![1，4][1_4]  
![1，4][1_4 1]  
shortest(1, 5)=2  
![1，5][1_5]

**运行结果：**

**范例输入：**

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70][]

**代码：**

void Dijkstra(AMGraph G,int v,int dist[],int path[])
    {
        int i,j,u,Min;
        int Set[MaxSize];
        for(i=0; i<G.n; i++)
        {
            dist[i] = G.arcs[v][i];     //初始化权值，v到i如果有边，则权值置权值，若无，则为MaxInt
            Set[i] = 0;                 //初始集合为空
            if(G.arcs[v][i]<MaxInt)     //将与v有连接的顶点的前驱置为v，无连接的置为-1
                path[i] = 0;
            else
                path[i] = -1;
        }
        Set[v] = 1;
        path[v] = -1;
        for(i=0; i<G.n-1; i++)
        {
            Min = MaxInt;
            for(j=0; j<G.n; j++)        //选出所有连接节点中权值最小的节点
            {
                if(Set[j]==0&&dist[j]<Min)
                {
                    u = j;
                    Min = dist[j];
                }
            }
            Set[u] = 1;
            for(j=0; j<G.n; j++)        //判断u的加入是否会出现通往顶点j的更短的路径，若出现，则更新权值
            {
                if(Set[j]==0&&dist[u]+G.arcs[u][j]<dist[j])
                {
                    dist[j] = dist[u]+G.arcs[u][j];
                    path[j] = u;
                }
            }
        }
    }

void PrintGraph(int path[],int dist[],int a)        //打印路径
    {
        int Stack[MaxSize],top = -1;
        printf("\n该路径的长度为:%d\n",dist[a]);
        while(path[a]!=-1)
        {
            Stack[++top] = a;
            a = path[a];
        }
        Stack[++top] = a;
        while(top!=-1)
        {
            printf("%d\t",Stack[top--]);
        }
    
    }

**完整代码：**

#include <stdio.h>
    #include <stdlib.h>
    #define MaxVertices 100
    #define MaxInt 100
    #define MaxSize 20
    typedef struct
    {
        int vexs[MaxVertices];
        int arcs[MaxVertices][MaxVertices];
        int n,e;
    } AMGraph;
    void CreateGraph(AMGraph &G)
    {
        int i,j,vi,vj,w;
        printf("请输入总顶点数和边数:\n");
        scanf("%d %d",&G.n,&G.e);
        printf("创建顶点表:\n");
        for(i=0; i<G.n; i++)
            scanf("%d",&G.vexs[i]);
        for(i=0; i<G.n; i++)
        {
            for(j=0; j<G.n; j++)
            {
                G.arcs[i][j] = MaxInt;
            }
        }
        printf("创建边表:\n");
        for(i=0; i<G.e; i++)
        {
            scanf("%d %d %d",&vi,&vj,&w);
            G.arcs[vi][vj] = w;
        }
    }
    void Dijkstra(AMGraph G,int v,int dist[],int path[])
    {
        int i,j,u,Min;
        int Set[MaxSize];
        for(i=0; i<G.n; i++)
        {
            dist[i] = G.arcs[v][i];     //初始化权值，v到i如果有边，则权值置权值，若无，则为MaxInt
            Set[i] = 0;                 //初始集合为空
            if(G.arcs[v][i]<MaxInt)     //将与v有连接的顶点的前驱置为v，无连接的置为-1
                path[i] = 0;
            else
                path[i] = -1;
        }
        Set[v] = 1;
        path[v] = -1;
        for(i=0; i<G.n-1; i++)
        {
            Min = MaxInt;
            for(j=0; j<G.n; j++)        //选出所有连接节点中权值最小的节点
            {
                if(Set[j]==0&&dist[j]<Min)
                {
                    u = j;
                    Min = dist[j];
                }
            }
            Set[u] = 1;
            for(j=0; j<G.n; j++)        //判断u的加入是否会出现通往顶点j的更短的路径，若出现，则更新权值
            {
                if(Set[j]==0&&dist[u]+G.arcs[u][j]<dist[j])
                {
                    dist[j] = dist[u]+G.arcs[u][j];
                    path[j] = u;
                }
            }
        }
    }
    void PrintGraph(int path[],int dist[],int a)        //打印路径
    {
        int Stack[MaxSize],top = -1;
        printf("\n该路径的长度为:%d\n",dist[a]);
        while(path[a]!=-1)
        {
            Stack[++top] = a;
            a = path[a];
        }
        Stack[++top] = a;
        while(top!=-1)
        {
            printf("%d\t",Stack[top--]);
        }
    
    }
    int main()
    {
        int i;
        int path[MaxSize],dist[MaxSize];
        AMGraph G;
        CreateGraph(G);
        Dijkstra(G,0,dist,path);
        for(i=1; i<G.n; i++)
        {
            PrintGraph(path,dist,i);
        }
    }

[SouthEast]: /images/20211116/ad5346cad13a44fc906072606410301e.png
[SouthEast 1]: /images/20211116/28f2135ecb78454fadcd46078299685a.png
[1_2]: /images/20211116/edc6c6bd70e4414dabab5e1996864ceb.png
[1_3]: /images/20211116/3d1a80bd0636420b89a4e454e7d1ca2a.png
[1_4]: /images/20211116/7a2fc30523cc42cdb61cf3eb91f009f2.png
[1_4 1]: /images/20211116/18c8a1898962485f8c39d796f074062f.png
[1_5]: /images/20211116/58533d73e5f34f9d9be62a286e497308.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70]: /images/20211116/50819cbf91aa4c9aa0146e0127552f0e.png