1.2 图算法-Floyd算法

图算法-Floyd算法

目录

• 图算法-Dijkstra算法
• 图算法-Floyd算法
• 图算法-Bellman-Ford算法
• 图算法-Prim算法
• 图算法-Kruskal算法

参考文献

• https://www.jianshu.com/p/f73c7a6f5a53
• https://blog.csdn.net/jeffleo/article/details/53349825

1 问题分析

• Floyd算法是一个经典的动态规划算法，它又被称为插点法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
• Floyd算法是一种利用动态规划的思想寻找给定的加权图中多源点最短路径的算法 ,算法目标是寻找从点i到点j的最短路径。

2 算法原理

• Floyd算法的基本思想：可以将问题分解:
  • 第一、先找出最短的距离
  • 第二、然后在考虑如何找出对应的行进路线。

以后再整理一下文字内容

3 算法过程

顶点名称和下标的对应

• A B C D E F G
• 0 1 2 3 4 5 6

1. 弗洛伊德算法定义了两个二维矩阵

   • 矩阵D记录顶点间的最小路径。例如D[0][3]= 10，说明顶点0 到 3 的最短路径为10；
   • 矩阵P记录顶点间最小路径中的中转点
   • 例如P[0][3]= 1 说明，0 到 3的最短路径轨迹为：0 -> 1 -> 3。

2. 它通过3重循环，k为中转点，v为起点，w为终点，循环比较D[v][w] 和 D[v][k] + D[k][w] 最小值，如果D[v][k] + D[k][w] 为更小值，则把D[v][k] + D[k][w] 覆盖保存在D[v][w]中。

3. 以A为中间点，原D矩阵中，D[B][G]的值为INF，即不存在B->G的最小路径，但是通过A为中间点，D[B][A] + D[A][G] = 12 + 14 = 26 小于 D[B][G] = INF， 所以D[B][A] + D[A][G] 为 B -> G的最小值，因此覆盖D[B][G] 为 26。

4. 以B为中间点，第2步后的D矩阵中，D[A][C]的值为INF， 但是通过B，D[A][B] + D[B][C] = 12 + 10 = 22 小于 D[A][C] = INF，所以D[A][B] + D[B][C] 为 A->C的最小路径，覆盖D[A][C]的值为22， 以此类推。

4 算法效率

时间复杂度为$O(n^3)$

5 算法实现

//这里是弗洛伊德算法的核心部分 
    //k为中间点 
    for(k = 0; k < G.vexnum; k++){
        //v为起点 
        for(v = 0 ; v < G.vexnum; v++){
            //w为终点 
            for(w =0; w < G.vexnum; w++){
                if(D[v][w] > (D[v][k] + D[k][w])){
                    D[v][w] = D[v][k] + D[k][w];//更新最小路径 
                    P[v][w] = P[v][k];//更新最小路径中间顶点 
                }
            }
        }
    }

#include<iostream>
#include<vector>
using namespace std;

struct Dis {
    string path;
    int value;
    bool visit;
    Dis() {
        visit = false;
        value = 0;
        path = "";
    }
};

class Graph{
private:
    int vertex_num;   //图的顶点个数
    int edge;
    // 如果顶点的表示是离散的应该加一层映射
    vector<vector<int>> arc; //邻接矩阵
public:
    // 测试用的默认构造函数
    Graph();
    //构造函数,从命令行输入
    Graph(int vertex_num_,int edge_);
    //打印所有的边
    void print_edge();
    // 打印整个邻接矩阵
    void print_arc();
    //求最短路径
    void Dijkstra(int begin);
    void Floyd();
};

Graph::Graph(){
    this->vertex_num = 7;
    this->edge=12;
    this->arc = vector<vector<int>>(vertex_num,vector<int>(vertex_num,INT_MAX));
    // cout<<vertex_num<<endl;
    // 初始化一个邻接矩阵.dijskra算法的图。
    arc[0][1]=12;
    arc[1][0]=12;
    arc[0][6]=14;
    arc[6][0]=14;
    arc[0][5]=16;
    arc[5][0]=16;
    arc[1][2]=10;
    arc[2][1]=10;
    arc[1][5]=7;
    arc[5][1]=7;
    arc[2][3]=3;
    arc[3][2]=3;
    arc[2][4]=5;
    arc[4][2]=5;
    arc[2][5]=6;
    arc[5][2]=6;
    arc[3][4]=4;
    arc[4][3]=4;
    arc[4][5]=2;
    arc[5][4]=2;
    arc[4][6]=8;
    arc[6][4]=8;
    arc[5][6]=9;
    arc[6][5]=9;
    // 对角线自己到自己是0
    for(int i=0;i<vertex_num;i++){
        arc[i][i]=0;
    }
}

// 从命令行输入一个邻接矩阵
Graph::Graph(int vertex_num_,int edge_){
    this->vertex_num=vertex_num_;
    this->edge=edge_;
    this->arc=vector<vector<int>>(vertex_num,vector<int>(vertex_num,INT_MAX));
    int beg=0,end=0,weight=0;
    for(int i=0;i<edge_;i++){
        cin>>beg>>end>>weight;
        arc[beg][end]=weight;
        // 如果是无向图则需要添加反向的路径
        arc[end][beg]=weight;
    }
}

void Graph::print_edge(){
    for(int i=0;i<vertex_num;i++){
        for(int j=0;j<vertex_num;j++){
            if(arc[i][j]<INT_MAX)
            cout<<"begin:"<<i<<"\tend:"<<j<<"\tweight:"<<arc[i][j]<<endl;
        }
    }
}


void Graph::print_arc(){
    for(int i=0;i<vertex_num;i++){
        for(int j=0;j<vertex_num;j++){
            cout<<arc[i][j]<<"\t";
        }
        cout<<endl;
    }
}
void Graph::Dijkstra(int begin){
    // 初始化结果集,到自己是0
    vector<int> result(vertex_num,INT_MAX);
    result[begin]=0;
    // 初始化距离集合，每次从中挑选
    vector<int> distance(vertex_num,INT_MAX);
    for(int i=0;i<vertex_num;i++){
        distance[i]=arc[begin][i];
    }
    for(int k=0;k<vertex_num-1;k++){
        // 从中挑选非零的最小值，使用0表示已经挑选到结果集合中。
        int min_distance=INT_MAX;
        int min_index=0;
        for(int i=0;i<vertex_num;i++){
            if(distance[i]!=0 && distance[i]<min_distance){
                min_distance=distance[i];
                min_index=i;
            }
        }
        // 添加到结果集合中，并更新删除distance集合。
        cout<<min_index<<endl;
        result[min_index]=min_distance;
        distance[min_index]=0;

        // 使用min_index更新距离集合
        for(int i=0;i<vertex_num;i++){
            if(distance[i]!=0 && arc[min_index][i]<INT_MAX){
                distance[i]=min(distance[i],min_distance+arc[min_index][i]);
            }
        }
    }

    for(int i=0;i<vertex_num;i++){
        cout<<"end:"<<i<<"\tweight:"<<result[i]<<endl;
    }

}

void Graph::Floyd(){
    // 初始化结果集合，一个用来记录最短距离，一个用来记录最短路径。
    vector<vector<int>> distance(arc);
    vector<vector<int>> path(vertex_num,vector<int>(vertex_num,0));
    int i,j,k;
    int temp;

    for(k=0;k<vertex_num;k++){
        for(i=0;i<vertex_num;i++){
            for(j=0;j<vertex_num;j++){
                temp=INT_MAX;
                if(distance[i][k]<INT_MAX && distance[k][j]<INT_MAX){
                    temp=distance[i][k]+distance[k][j];
                }
                if(temp<distance[i][j]){
                    distance[i][j]=temp;
                    path[i][j]=k;
                }
            }
        }

    }
    for(i=0;i<vertex_num;i++){
        for(j=0;j<vertex_num;j++){
            cout<<distance[i][j]<<"\t";
        }
        cout<<endl;
    }
}

int main(){
    Graph g;
    // g.print();
    // g.Dijkstra(3);
    g.Floyd();
    return 0;
}