最短路径-Floyd(弗洛伊德)算法

缺乏、安全感 2022-05-14 03:42 271阅读 0赞

*  # 最短路径-Floyd(弗洛伊德)算法 #

--------------------

*  ## 简介： ##

相较Dijkstra，**Floyd是一个完全穷举图中每个点到末尾点的最短路径**

*  ## 算法思想： ##

### 按惯例说两个工具 ###

***Path\[MAX\_SIZE\]\[MAX\_SIZE\]：***保存所有的最短路径（指向）

***Short\_Path\[MAX\_SIZE\]\[MAX\_SIZE\]：***保存所有的最短路径长度（数组）

### 状态转移： ###

***Short\_Path\[v\]\[w\]=min\{ D\[v\]\[w\] , D\[v\]\[k\] + D\[k\]\[w\] \}***

**v-w为一路径，中间经过k，取最小路径的经过点k**

*  ## Dijkstra算法： ##

### 传送门：[最短路径-Dijkstra(迪杰斯特拉)算法][-Dijkstra] ###

### Dijkstra算法复杂度：O(n^n) ###

### Floyd算法复杂度：O(n^3) ###

*  ## Floyd模板： ##

#include<iostream>
    #include<cstdio>
    using namespace std;
    #define MAX_SIZE 1024
    
    //邻接图
    struct MGrapth
    {
        int Vexs[MAX_SIZE];  //顶点表
        int Arc[MAX_SIZE][MAX_SIZE];  //邻接矩阵
        int Num_Vertext,Num_Edges;  //顶点数，边数
    };
    MGrapth Map;
    
    int Path[MAX_SIZE][MAX_SIZE];  /*路径矩阵*/
    int Short_Path[MAX_SIZE][MAX_SIZE];   /*最短路矩阵*/
    
    void Floyd()
    {
        int v,w,k;
        for(v=0;v<Map.Num_Vertext;++v)
        {
            for(w=0;w<Map.Num_Vertext;w++)
            {
                Short_Path[v][w]=Map.Arc[v][w];
                Path[v][w]=w;
            }
        }
    
        for(k=0;k<Map.Num_Vertext;k++)
        {
            for(v=0;v<Map.Num_Vertext;v++)
            {
                for(w=0;w<Map.Num_Vertext;w++)
                {
                    if(Short_Path[v][w]>Short_Path[v][k]+Short_Path[k][w])
                    {
                        Short_Path[v][w]=Short_Path[v][k]+Short_Path[k][w];
                        Path[v][w]=Path[v][k];
                    }
                }
            }
        }
    }
    
    void Print_Path()   
    {
        int v,w,k;
        for(v=0;v<Map.Num_Vertext;v++)   //打印所有v-w的路径
        {
            for(w=v+1;w<Map.Num_Vertext;w++)
            {
                printf("v%d-v%d weight: %d",v,w,Short_Path[v][w]);
                k=Path[v][w];
                printf(" Path: %d",v);
                while(k!=w)
                {
                    printf(" -> %d",k);
                    k=Path[k][w];
                }
                printf("-> %d\n",w );
            }
            printf("\n");
        }
    }

[-Dijkstra]: https://blog.csdn.net/SZU_Crayon/article/details/82290234