Dijkstra算法

邻接矩阵版

#include <bits/stdc++.h>

using namespace std;

const int maxn=1010;
const int INF=0x3f3f3f3f;
int n,m,s,G[maxn][maxn];//n为顶点数，m为边数，s为起点
int d[maxn];//到达各点的最短路径长度
bool vis[maxn]={false};

void Dijkstra(int s)
{
    fill(d,d+maxn,INF);
    d[s]=0;
    for(int i=0;i<n;i++)//n个顶点循环n次
    {
        int u=-1,minn=INF;
        for(int j=0;j<n;j++)
        {
            if(!vis[j]&&d[j]<minn)
            {
                u=j;
                minn=d[j];
            }
        }//若找不到小于INF的数组d则可证明改点于起点不连通
        if(u==-1) return;
        vis[u]=true;
        for(int v=0;v<n;v++)
        {
            if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v])
            {
                d[v]=d[u]+G[u][v];//优化数组d
            }
        }
    }

}