循环N次
算法分为两部分：
1）找到距离最小的城市，找不到距离更小的城市时退出方法
2）更新距离
实际操作时，先初始化：
更新dis为INF，更新dis[start] = 0；
变种：
void print_path(int start){ if(path[start]==start)printf("%d ",start); else{ print_path(path[start]); printf("%d ",start); } }
普通版本代码：
#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAXV=1000; const int INF=0x3FFFFFFF; struct Node{ int v, dis; }; vector<Node> Adj[MAXV]; int n; int d[MAXV]; bool vis[MAXV]={false}; void Dijkstra(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++){ if(vis[v]==false&&(MIN+Adj[u][j].dis)<d[v]){ d[v]=d[u]+Adj[u][j].dis; } } } }
原文：https://www.cnblogs.com/flipped415/p/10405471.html