Dijkstra算法实现——————数据结构作业

青旅半醒 2022-04-17 05:27 159阅读 0赞

*  邻接矩阵存图
 *  输入顶点个数n，边的个数m
 *  输入m条边
 *  输入起点 v 0 \\ v\_0 v0 和终点 v \\ v v
 *  输出最短路径及路径长度

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    
    const int MaxInt = 32767;//INF
    const int MVNum  = 1e2+7;//最大顶点数
    typedef char VerTexType;
    typedef int  ArcType;
    typedef struct{
        
            VerTexType vexs[MVNum];
            ArcType arcs[MVNum][MVNum];
            int vexnum,arcnum;
    }AMGraph;
    
    bool S[MVNum];//记录源点v0到终点vi是否已被确定的最短路径长度，true 表示确定，false表示尚未确定
    int D[MVNum];//记录源点v0到终点vi的当前最短路径长度，D[i]需要初始化
    int Path[MVNum];
    
    int GreateUDN(AMGraph &G)
    {
        
            cout<<"请输入总的顶点数和总边数:\n";
            cin>>G.vexnum>>G.arcnum;//输入总顶点数，总边数
            /*
            for(int i=0;i<G.vexnum; ++i)//输入点的信息,不过这个没有用上
                    cin>>G.vexs[i];
            */
            cout<<"请输入"<<G.arcnum<<"条边:"<<endl;
            for(int i=0; i<=G.vexnum; ++i)
                    for(int j=0;j<=G.vexnum;++j)
                            G.arcs[i][j]=MaxInt;
            for(int k=0; k<G.arcnum; ++k)//构造邻接矩阵
            {
        
                    int v1,v2,w;
                    cin>>v1>>v2>>w;
                    G.arcs[v1][v2] = G.arcs[v2][v1] = w;
            }
    
            return 1;
    }
    
    void ShortestPath_DIJ(AMGraph G,int v0)//用Dijkstra算法求单源最短路
    {
        
            int  n = G.vexnum;// n 为G中顶点的个数
            for(int v = v0; v<=n; ++v)//n 个定点依次初始化
            {
        
                    S[v] = false;//S初始是空集
                    D[v] = G.arcs[v0][v];//
                    if(D[v] < MaxInt)       Path[v] = v0;
                    else                    Path[v] = -1;
            }
            S[v0] = true;
            D[v0] = 0;
            int v;
            for(int i=1; i<=n; ++i)
            {
        
                    int minn = MaxInt;
                    for(int w=0; w<=n; ++w)
                            if(!S[w] && D[w] < minn)
                            {
        
                                    v = w;
                                    minn = D[w];
                            }
    
                    S[v] = true;
                    for(int w=0; w<=n; ++w)
                            if(!S[w] && (D[v] + G.arcs[v][w] < D[w]))
                            {
        
                                    D[w] = D[v] + G.arcs[v][w];
                                    Path[w] = v;
                            }
            }
    }
    
    
    int main()
    {
        
            AMGraph G;
            GreateUDN(G);
            int v0,v=5;
            printf("请输入起点和终点:");
            scanf("%d %d",&v0,&v);
            ShortestPath_DIJ(G,v0);
            printf("%d\n",D[v]);
            for(int i=v;~i; i=Path[i])
            {
        
                    if(i != v)      printf("<-");
                    printf("%d",i);
            }
            puts("");
            return 0;
    }