迪克斯特拉（Dijkstra）算法单源最短路径

￡神魔★判官ぃ 2022-05-27 02:09 177阅读 0赞

输入

第一行输入定点数N

第i行 s(起结点) k(与起结点相连的组数) g(终结点) v（权值）

#include<stdio.h>
    #include<string.h>
    #define max 1000
    #define INF 999999
    int m[max][max];  //m[s][g]中记录s到g的边的权值
    int d[max];       //d[v]记录起点到v边的权值
    int visit[max];   //visit[v]记录v的访问状态
    int n;
    void dijkstra()
    {
        d[0]=0;
        while(1)
        {
            int min=INF,u;
            int flag=1;
            for(int i=0;i<n;i++)
            {
                if(d[i]<min&&visit[i]==0)
                {
                    min=d[i];
                    u=i;
                    flag=0;
                }
            }
            visit[u]=1;
            if(flag) break;
            for(int i=0;i<n;i++)
            {
                if(d[i]>(d[u]+m[u][i]))
                {
                    if(visit[i]==0)
                    {
                        d[i]=d[u]+m[u][i];
                    }
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            printf("0到%d的最短距离为:%d\n",i,d[i]);
        }
    }
    int main()
    {
        while(scanf("%d",&n)!=EOF)
        {
            memset(visit,0,sizeof(visit));
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    m[i][j]=INF;
                }
                d[i]=INF;
            }
            int t=n;
            while(t--)
            {
                int s,m1,g,v;
                scanf("%d%d",&s,&m1);
                for(int i=0;i<m1;i++)
                {
                    scanf("%d%d",&g,&v);
                    m[s][g]=v;
                }
            }
            dijkstra();
        }
        return 0;
    }

![Center][]

[Center]: /images/20220527/d71276898b424f098e135b160047563b.png