C++——迪杰斯特拉算法&弗洛伊德算法(Dijkstra&Floyd)for Neuedu

╰半夏微凉° 2022-11-15 14:12 211阅读 0赞

## *采用迪杰斯特拉算法和弗洛伊德算法* ##

> 求出两个景点间的最短路径和最短距离

*  例如下图所示的无向图：  
    通过输入节点个数和线路条数，分别输入各线路权值进行计算最短(最优)线路。
 *  Ps：使用Qt进行编译运行

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dvZE91Tw_size_16_color_FFFFFF_t_70_pic_center]

/* * 基于最短路径的景点规划 * 简介：分别采用迪杰斯特拉算法和弗洛伊德算法，求出两个景点间的最短路径和最短距离。 * 作者：181203616-宋明桥-GodOuO * 修改履历： * 21年4月，创建文件 */
    
    #include<iostream>
    #include<string>
    using namespace std;
    
    class Dis { 
    public:
        Dis() { 
            visit = false;
            value = 0;
            path = "";
        }
    public:
    string path;
        int value;
        bool visit;
    };
    class Graph_fld { 
    public:
        Graph_fld(int vexnum, int edge);
        ~Graph_fld();
        bool check_edge_value(int start, int end, int weight);
        void createGraph(int);
        void Floyd();
        void print_path(int);
        void print();
    private:
        int vexnum;
        int edge;
        int **arc;
        int ** dis;
        int ** path;
    };
    class Graph_dis { 
    public:
        Graph_dis(int vexnum, int edge);
        ~Graph_dis();
        bool check_edge_value(int start, int end, int weight);
        void createGraph();
        void print();
        void Dijkstra(int begin);
        void print_path(int);
    private:
        int vexnum;   //图的顶点个数
        int edge;     //图的边数
        int **arc;   //邻接矩阵
        Dis * dis;   //记录各个顶点最短路径的信息
    };
    
    Graph_fld::Graph_fld(int vexnum, int edge) { 
        this->vexnum = vexnum;
        this->edge = edge;
        arc = new int*[this->vexnum];
        dis = new int*[this->vexnum];
        path = new int*[this->vexnum];
        for (int i = 0; i < this->vexnum; i++) { 
            arc[i] = new int[this->vexnum];
            dis[i] = new int[this->vexnum];
            path[i] = new int[this->vexnum];
            for (int k = 0; k < this->vexnum; k++) { 
                arc[i][k] = INT_MAX;
            }}}
    Graph_dis::Graph_dis(int vexnum, int edge) { //初始化顶点数和边数
        this->vexnum = vexnum;
    this->edge = edge;
    arc = new int*[this->vexnum];
        dis = new Dis[this->vexnum];
        for (int i = 0; i < this->vexnum; i++) { 
            arc[i] = new int[this->vexnum];
            for (int k = 0; k < this->vexnum; k++) { 
                    arc[i][k] = INT_MAX;
            }}}
    
    Graph_fld::~Graph_fld() { 
        for (int i = 0; i < this->vexnum; i++) { 
            delete this->arc[i];
            delete this->dis[i];
            delete this->path[i];
        }
        delete dis;
        delete arc;
        delete path;
    }
    Graph_dis::~Graph_dis() { 
        delete[] dis;
        for (int i = 0; i < this->vexnum; i++) { 
            delete this->arc[i];
        }
        delete arc;
    }
    
    bool Graph_fld::check_edge_value(int start, int end, int weight) { 
        if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) { 
            return false;
        }
        return true;
    }
    bool Graph_dis::check_edge_value(int start, int end, int weight) { 
        if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) { 
            return false;
        }
        return true;
    }
    
    
    void Graph_fld::createGraph(int kind) { 
        cout << "请输入每条边的起点和终点（顶点编号从1开始）以及其权重：('1 2 8'-“V1到V2距离为8”)" << endl;
        int start;
        int end;
        int weight;
        int count = 0;
        while (count != this->edge) { 
            cin>>start>>end>>weight;
            while (!this->check_edge_value(start,end,weight)) { 
                cout<<"输入的边的信息不合法，请重新输入"<<endl;
                cin>>start>>end>>weight;
            }
            arc[start - 1][end - 1] = weight;
            if(2==kind)
                arc[end-1][start-1] = weight;
            ++count;}}
    void Graph_dis::createGraph() { 
        cout << "请输入每条边的起点和终点（顶点编号从1开始）以及其权重" << endl;
        int start;
        int end;
        int weight;
        int count = 0;
        while (count != this->edge) { 
            cin >> start >> end >> weight;
                    while (!this->check_edge_value(start, end, weight)) { 
                cout << "输入的边的信息不合法，请重新输入" << endl;
                cin >> start >> end >> weight;
            }
        arc[start - 1][end - 1] = weight;
            arc[end - 1][start - 1] = weight;
            ++count;
        }}
    
    void Graph_fld::Floyd() { 
        int i=0,j=0;
        for (i= 0; i< this->vexnum; i++) { 
            for (j=0; j< this->vexnum; j++) { 
                this->dis[i][j] = this->arc[i][j];
                this->path[i][j] = j;}}
        int n=0;
        for (int m = 0;m<this->vexnum;m++) { 
            for (i = 0;i < this->vexnum; i++) { 
                for (j = 0; j< this->vexnum; j++) { 
                    n=(dis[i][m]==INT_MAX||dis[m][j] == INT_MAX)?INT_MAX:(dis[i][m] + dis[m][j]);
                    if (this->dis[i][j]>n) { 
                        this->dis[i][j]=n;
                        this->path[i][j]=this->path[i][m];
                    }}}}}
    void Graph_dis::Dijkstra(int begin){ 
        int i;
        for (i = 0; i < this->vexnum; i++) { 
            dis[i].path = "v" + to_string(static_cast<long long>(begin)) + "-->v" + to_string(static_cast<long long>(i + 1));
            dis[i].value = arc[begin - 1][i];
        }
        dis[begin - 1].value = 0;
        dis[begin - 1].visit = true;
        int count = 1;
        while (count != this->vexnum) { 
            int temp=0;
            int min = INT_MAX;
            for (i = 0; i < this->vexnum; i++) { 
                if (!dis[i].visit && dis[i].value<min) { 
                    min = dis[i].value;
                    temp = i;
                }}
            dis[temp].visit = true;
            ++count;
            for (i = 0; i < this->vexnum; i++) { 
                if (!dis[i].visit && arc[temp][i]!=INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) { 
                    dis[i].value = dis[temp].value + arc[temp][i];
                    dis[i].path = dis[temp].path + "-->v" + to_string(static_cast<long long>(i + 1));
                }}}}
    
    void Graph_fld::print() { 
        cout << "图的邻接矩阵为：" << endl;
        int i = 0; //i代表打印行
        int j = 0; //j代表打印列
        while (i != this->vexnum) { 
            j = 0;
            while (j!= this->vexnum) { 
                if (arc[i][j] == INT_MAX)
                    cout << "∞" << " ";
                else
                    cout << arc[i][j] << " ";
                ++j;
            }
            cout << endl;
            ++i;
        }}
    void Graph_dis::print() { 
        cout << "图的邻接矩阵为：" << endl;
        int i= 0; //打印行
        int j= 0; //打印列
        while (i != this->vexnum) { 
            j= 0;
            while (j!= this->vexnum) { 
                if (arc[i][j] == INT_MAX)
                    cout << "∞" << " ";
                else
                cout << arc[i][j] << " ";
                ++j;}
            cout << endl;
            ++i;
        }}
    
    void Graph_fld::print_path(int begin) { 
        cout << "各个顶点对的最短路径：" << endl;
        int i = 0;
        int j = 0;
        int m = 0;
        for (i=begin-1;i<begin;i++) { 
            for (j= 0; j< this->vexnum;j++) { 
                if(0!=(to_string(static_cast<long long>(i+ 1)).compare(to_string(static_cast<long long>(j+ 1))))){ 
                    cout << "v" << to_string(static_cast<long long>(i+ 1)) << "---" << "v" << to_string(static_cast<long long>(j+ 1)) << "最短路径长度为： "
                         << this->dis[i][j] << "\n\t\t\t最短路径为： " << "v" << to_string(static_cast<long long>(i+ 1));
                    m = path[i][j];
                    while (m!= j) { 
                        cout << "-->" << "v" << to_string(static_cast<long long>(m + 1));
                        m= path[m][j];
                    }
                    cout << "-->" << "v" << to_string(static_cast<long long>(j + 1));
    
                    cout << endl;}
                else{ cout << "v" << to_string(static_cast<long long>(i+ 1)) << "---" << "v" << to_string(static_cast<long long>(j+ 1)) << "最短路径长度为： "
                          <<0 << "\n\t\t\t最短路径为： v" << to_string(static_cast<long long>(i+ 1)) << "-->v"<<to_string(static_cast<long long>(j+ 1))<<endl;}
            }}}
    void Graph_dis::print_path(int begin) { 
        string str;
        str = "v" + to_string(static_cast<long long>(begin));
        cout << "以"<<str<<"为起点的图的最短路径为：" << endl;
        for (int i = 0; i != this->vexnum; i++) { 
            if(dis[i].value!=INT_MAX)
                cout<<str<<"---v"<<i+1<<"最短路径长度为： "<< dis[i].value <<"\n\t\t\t最短路径为： "<<dis[i].path<<endl;
            else { 
                cout << dis[i].path << "当前没有最短路径" << endl;
            }}}
    
    bool check(int Vexnum, int edge) { 
        if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
            return false;
        return true;}
    
    int main() { 
        int vexnum=0; int edge=0; int sel=0; int s=0;
        while(1){ 
            cout<<"\n输入数字运行功能 \n 1.基于迪杰斯特拉算法最短路径计算 \n 2.基于和弗洛伊德算法最短路径计算 \n 3.Quit \n"<<endl;
            cin>>s;
    
            if(1==s){ //迪杰斯特拉算法
                cout << "\n输入图的顶点个数和边的条数：('3 2'-“3顶点，2条线”)" << endl;
                cin >> vexnum >> edge;
                while (!check(vexnum, edge)) { 
                    cout << "输入的数值不合法，请重新输入" << endl;
                    cin >> vexnum >> edge;}
                Graph_dis graph(vexnum, edge);
                graph.createGraph();
                graph.print();
    
                while(1){ 
                    s=0;
                    cout<< "\n 输入数字运行功能 \n 1.运行计算 \n 2.Quit \n" <<endl;
                    cin>>s;
                    if(1==s){ 
                        cout<< "请输入初始点，输入后将遍历所有节点最短距离：('1'-V1点出发到各点最短路径)" <<endl;
                        cin>>sel;
                        graph.Dijkstra(sel);
                        graph.print_path(sel);}
                    else if(2==s){ 
                        break;
                    }else{ 
                        cout<<"请输入正确值！"<<endl;
                    }}}
    
            else if(2==s){ //弗洛伊德算法
                cout << "输入图的顶点个数和边的条数：('3 2'-“3顶点，2条线”)" << endl;
                cin >> vexnum >> edge;
                while (!check(vexnum, edge)) { 
                    cout << "输入的数值不正确，请重新输入" << endl;
                    cin >> vexnum >> edge;}
                Graph_fld graph(vexnum, edge);
                graph.createGraph(2);
                graph.print();
    
                while(1){ 
                    s=0;
                    cout<< "\n 输入数字运行功能 \n 1.运行计算 \n 2.Quit \n" <<endl;
                    cin>>s;
                    if(1==s){ 
                        cout<< "请输入初始点，输入后将遍历所有节点最短距离：('1'-V1点出发到各点最短路径)" <<endl;
                        cin>>sel;
                        graph.Floyd();
                        graph.print_path(sel);}else if(2==s){ 
                        break;
                    }else{ 
                        cout<<"请输入正确值！"<<endl;
                    }}}
    
            else if(3==s){ //Quit
                cout<<"BYE!"<<endl;
                system("pause");
                return 0;
            }else{ 
                cout<<"请输入正确数字！"<<endl;
            }}}

*  运行截图实例：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dvZE91Tw_size_16_color_FFFFFF_t_70_pic_center 1]  
*进行运算：*

**MENU：**  
![在这里插入图片描述][20210401203126228.png_pic_center]

**Dijkstra：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dvZE91Tw_size_16_color_FFFFFF_t_70_pic_center 2]

**Floyd**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dvZE91Tw_size_16_color_FFFFFF_t_70_pic_center 3]

*  在计算中发现迪杰斯特拉算法的缺陷，故推荐使用弗洛伊德算法进行线路优化计算！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dvZE91Tw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/fa09c370042242c48d6efc21bbdaa2d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dvZE91Tw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/832e9d46253347e1be0e061d828a0a35.png
[20210401203126228.png_pic_center]: /images/20221022/b41976275e78417c90bf5a9f42470eb4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dvZE91Tw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/459c3568b5d748c2af0d1dce24ed30d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dvZE91Tw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221022/c2e15470118a474e88d292477f89dd53.png