Dijkstra算法模板

落日映苍穹つ 2022-05-30 08:24 199阅读 0赞

#include <bits/stdc++.h>
    //定义邻接矩阵的大小
    #define N 100
    #define M 100
    
    using namespace std;
    
    typedef struct node {
        int map[N][M];//邻接矩阵
        int n;//顶点数
        int e;//边数
    }MGragh;
    
    
    void dijkstra(MGragh g,int *dis,int *pre,int v0){
        int i,j,k;
        bool *visited=(bool *)malloc(sizeof(bool)*g.n);//标记数组
        for(i=0;i<g.n;i++){//初始化
            if(g.map[v0][i]>0&&i!=0){
                dis[i]=g.map[v0][i];
                pre[i]=v0;
            }
            else{
                dis[i]=INT_MAX;
                pre[i]=-1;
            }
            pre[v0]=v0;
            dis[v0]=0;
        }
        visited[v0]=true;//标记源点v0为访问过
        for(i=1;i<g.n;i++){//运行n-1次
            int min=INT_MAX;//初始化
            int u;
            for(j=0;j<g.n;j++){//寻找未访问过的顶点中权值最小的那个
                if(visited[j]==false&&dis[j]<min){
                    min=dis[j];//记录下来
                    u=j;
                }
            }
            visited[u]=true;//标记为访问过
            //更新dis数组的值和路径
            for(k=0;k<g.n;k++){
                if(visited[k]==false&&g.map[u][k]>0&&g.map[u][k]+min<dis[k]){
                    dis[k]=min+g.map[u][k];
                    pre[k]=u;
                }
            }
        }
    }
    
    void showpath(int *pre,int v,int v0){//v是当前节点，
        //输出源点v0到当前节点v的路径
        stack<int>s;
        while(v!=v0){
            s.push(v);
            v=pre[v];
        }
        s.push(v);
        while(!s.empty()){
            printf("%d ",s.top());
            s.pop();
        }
    }
    
    
    int main()
    {
        int n,e;
        while(scanf("%d%d",&n,&e)&&e!=0){
            int i,j;
            int s,t,w;//起始点s，终点t，边st的权值为w
            MGragh g;
            int v0;//源点v0
            int *dis=(int *)malloc(sizeof(int)*n);//dis[i]记录从源点v0到当前点i的路径长度
            int *pre=(int *)malloc(sizeof(int)*n);//记录每个点的前驱，即pre[i]=j;说明i点的前驱为j
            for(i=0;i<N;i++){//初始化
                for(j=0;j<M;j++){
                    g.map[i][j]=0;
                }
            }
            g.n=n;
            g.e=e;
            for(i=0;i<e;i++){//建立邻接矩阵
                scanf("%d%d%d",&s,&t,&w);
                g.map[s][t]=w;
            }
            scanf("%d",&v0);
            
            dijkstra(g,dis,pre,v0);
            for(i=0;i<n;i++){
                if(i!=v0){
                    showpath(pre,i,v0);//输出路径
                    printf("%d\n",dis[i]);//输出最短路径的大小
                }
            }
        }
        return 0;
    }
    /*
    测试用例
    5 7
    0 1 100
    0 2 30
    0 4 10
    2 1 60
    2 3 60
    3 1 10
    4 3 50
    0
    */