图_dijkstra算法【数据结构实践报告】

超、凢脫俗 2022-06-03 08:17 174阅读 0赞

**数据结构实验报告**

**实验名称**： 实验七 图 dijkstra算法

学号：\*\*\*

姓名：gnosed

实验日期：2017.12.23

**一、实验目的**

掌握求最短路径的Dijkstra算法

**二、实验具体内容**

**1、实验题目1：**

**（1）题目**

编写程序，用Dijkstra算法求图的最短路径

**（2）分析**

存储结构：

1.  图以邻接矩阵表示，关系矩阵对角线初值取为0。
2.  数组dist\[\]:dist\[i\]最终储存Vo到Vi的最短路径及最短路径上Vi的前驱顶点（计算过程为距离值，可能会被调整）。

说明：

1.  dist可分为集合U和V两部分，U指从Vo到一个顶点最短路径的所有顶点，V指未确定最短路径的顶点集合。
2.  初始化dist时，集合U只有Vo，其对应的距离值为0；集合V中Vi的距离值为边（Vo，Vi）的权，若Vo和Vi之间无直接边，则Vi的距离值为无穷大（这里定为1000）。

算法过程：

1）从集合V中选择距离值最小的顶点Vmin加入到集合U（可通过修改对角线元素值为1来表示）

2）因为上面选出的Vmin放到U时，如果Vmin可能是Vo到其它顶点V\[i\]最短路径上的一个顶点，这使得dist\[i\]的距离值减小，所以这时，需要根据min值，对集合V中各顶点的距离值进行调整：如果Vo到Vi的距离值比原来的距离值小，则修改Vi的距离值dist\[i\].length，否则不修改。

3）重复1）2），直到从Vo可以到达的所有顶点都被放入集合U为止。

**（3）实验代码**

源代码：

#include <iostream>
    #include <stack>
    #define Vextype int
    #define Adjtype int
    #define VN 6
    #define MAX 1000
    using namespace std;
    
    struct GraphMatrix
    {
        Vextype vex[VN][VN];
        Adjtype arc[VN][VN];
    };
    typedef struct{
        Adjtype length;//shortest path
        int prevex;//Vi的前驱顶点
    }Path;
    Path dist[VN];
    void init(GraphMatrix *pgraph,Path *dist)
    {
        dist[0].length=dist[0].prevex=0;
        pgraph->arc[0][0]=1;//用矩阵对角线元素表示U，为1表示在U中
        for(int i=1;i<VN;++i){//初始化U-V中顶点的距离值
            dist[i].length=pgraph->arc[0][i];
            if(dist[i].length!=MAX) dist[i].prevex=0;
            else dist[i].prevex=-1;
        }
    }
    void dijkstra(GraphMatrix *pgraph,Path *dist)
    {
        init(pgraph,dist);//初始化，U中只有Vo
        Adjtype minw;
        int mv;
        for(int i=1;i<VN;++i){
            minw=MAX; mv=0;
            for(int j=1;j<VN;++j)//在V-U中选出距离Vo最近的顶点
                if(pgraph->arc[j][j]!=1 && minw>dist[j].length){
                    minw=dist[j].length; mv=j;
                }
            if(mv==0)    break;//Vo与V-U的顶点不连通，结束
            pgraph->arc[mv][mv]=1;//顶点mv加入U
            for(int i=1;i<VN;++i){//调整V-U顶点的已知最短路径
                if(pgraph->arc[i][i]!=1&&
                   dist[i].length>dist[mv].length+pgraph->arc[mv][i]){
                       dist[i].prevex=mv;
                        dist[i].length=dist[mv].length+pgraph->arc[mv][i];
                   }
            }
        }
    }
    
    int main()
    {
        GraphMatrix *G=new struct GraphMatrix;
        for(int i=0;i<VN;i++)
            for(int j=0;j<VN;j++)
                cin>>G->arc[i][j];
        dijkstra(G,dist);
        cout<<"起点是0，请输入终点:";
        int en,k;
        cin>>en;
        k=en;
        cout<<"最短路径长度:"<<dist[k].length<<"\n路径:";
        stack<int> Path;
        while(1){
            Path.push(dist[k].prevex);
            k=dist[k].prevex;
            if(!k) break;
        }
        while(!Path.empty()){
            cout<<Path.top()<<"->";
            Path.pop();
        }
        cout<<en;
        return 0;
    }

Input

0 50 101000 45 1000
    1000 0 15 1000 5 1000
    20 1000 0 15 1000 1000
    1000 20 1000 0 35 1000
    1000 1000 1000 30 0 1000
    1000 1000 1000 3 1000 0

Output:

起点是0，请输入终点:3
    最短路径长度:25
    路径:0->2->3