1 邻接矩阵版
const int maxv=1000;
const int inf=1000000000;//邻接矩阵版
int n,m,s,g[maxv][maxv]; //n为顶点数，m为边数，s为起点，maxv为最大顶点数
int d[maxv]; //起点到各点的最短路径长度
bool vis[maxv]={false}; //标记是否已访问 void dijkstra1(int s){ //s为起点 fill(d,d+maxv,inf); //fill函数将整个d数组赋为inf d[s]=0; //起点s到达自身的距离为0 for(int i=0;i<n;i++){ //循环n次 int u=-1,min=inf; //u使得d[u]最小，min存放该最小的d[u] for(int j=0;j<n;j++){ //找到未访问的顶点中d[]最小的 if(vis[j]==false&&d[j]<min){u=j;min=d[j];} }//找不到小于inf的d[u],说明剩下的顶点和起点s不连通if(u==-1) return;vis[u]=true; //标记u为已访问for(int v=0;v<n;v++){//如果v未访问&&u能到达v&&以u为中介点可以使d[v]更优if(vis[v]==false&&g[u][v]!=inf&&d[u]+g[u][v]<d[v])d[v]=d[u]+g[u][v]; //优化d[v] } }
}
2 邻接表版
//邻接表版
struct Node{int v,dis; //v为边的目标顶点，dis为边权
};vector<Node> adj[maxv];void dijkstra2(int s){fill(d,d+maxv,inf);d[s]=0;for(int i=0;i<n;i++){int u=-1,min=inf;for(int j=0;j<n;j++){if(vis[j]==false&&d[j]<min){u=j;min=d[j];}}if(u==-1) return;vis[u]=true;for(int j=0;j<adj[u].size();j++){int v=adj[u][j].v; //通过邻接表直接获得u能到达的顶点v if(vis[v]==false&&d[u]+adj[u][j].dis<d[v])d[v]=d[u]+adj[u][j].dis;}}
}