图的应用——弗洛伊德两点最短路径

深藏阁楼爱情的钟 2021-11-18 00:24 286阅读 0赞

> Dijkstra算法是求图中**某一顶点到其余各顶点的最短路径，**如果求图中**任意一对顶点间的最短路径**，则通常使用弗洛伊德算法

**Floyd算法：**

**运行结果:**

**输入：**  
4 8  
0 1 2 3  
0 1 5  
0 3 7  
1 2 4  
1 3 2  
2 0 3  
2 1 3  
2 3 2  
3 2 1

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70][]

void Floyd(AMGraph G,int path[][MaxVertices])
    {
        int i,j,k;
        int n = G.n;
        int A[MaxVertices][MaxVertices];
        for(i=0; i<n; i++)      //初始化A数组和path数组，path数组保存着两点间的最短路径
        {
            for(j=0; j<n; j++)
            {
                A[i][j] = G.arcs[i][j];
                path[i][j] = -1;
            }
        }
        for(k=0; k<n; k++)
        {
            for(i=0; i<n; i++)
            {
                for(j=0; j<n; j++)
                {
                    if(A[i][j] > (A[k][j]+A[i][k]))     //如果前者大于后者，则说明i，j顶点之间有中间顶点可以使两点路径更短
                    {
                        A[i][j] = (A[i][k]+A[k][j]);    //更新权值
                        path[i][j] = k;                 //path数组保存中间顶点
                    }
                }
            }
        }
    }

**打印最短路径：**

void PrintPath(int u,int v,int path[][MaxVertices])
    {
        if(path[u][v] == -1)        //如果path值为1，则说明此时u，v相连，二者之间无中间顶点
        {
            printf("%d\t",v);
        }
        else
        {
            int mid = path[u][v];   //mid即为中间顶点
            PrintPath(u,mid,path);
            PrintPath(mid,v,path);
        }
    }

**完整代码：**

#include <stdio.h>
    #include <stdlib.h>
    #define MaxVertices 20
    #define MaxInt 100
    typedef struct
    {
        int vexs[MaxVertices];
        int arcs[MaxVertices][MaxVertices];
        int n,e;
    } AMGraph;
    void CreateGraph(AMGraph &G)
    {
        int i,j,w,vi,vj;
        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++)
            {
                if(i==j)
                {
                    G.arcs[i][j] = 0;
                }
                else
                {
                    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 Floyd(AMGraph G,int path[][MaxVertices])
    {
        int i,j,k;
        int n = G.n;
        int A[MaxVertices][MaxVertices];
        for(i=0; i<n; i++)      //初始化A数组和path数组，path数组保存着两点间的最短路径
        {
            for(j=0; j<n; j++)
            {
                A[i][j] = G.arcs[i][j];
                path[i][j] = -1;
            }
        }
        for(k=0; k<n; k++)
        {
            for(i=0; i<n; i++)
            {
                for(j=0; j<n; j++)
                {
                    if(A[i][j] > (A[k][j]+A[i][k]))     //如果前者大于后者，则说明i，j顶点之间有中间顶点可以使两点路径更短
                    {
                        A[i][j] = (A[i][k]+A[k][j]);    //更新权值
                        path[i][j] = k;                 //path数组保存中间顶点
                    }
                }
            }
        }
    }
    void PrintPath(int u,int v,int path[][MaxVertices])
    {
        if(path[u][v] == -1)        //如果path值为1，则说明此时u，v相连，二者之间无中间顶点
        {
            printf("%d\t",v);
        }
        else
        {
            int mid = path[u][v];   //mid即为中间顶点
            PrintPath(u,mid,path);
            PrintPath(mid,v,path);
        }
    }
    int main()
    {
        int u,v;
        int path[MaxVertices][MaxVertices];
        AMGraph G;
        CreateGraph(G);
        Floyd(G,path);
        printf("请输入查询的顶点:\n");
        scanf("%d %d",&u,&v);
        printf("%d\t",u);
        PrintPath(u,v,path);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70]: /images/20211116/031b98f293b94a7c8077e2acb166faad.png