Dijkstra算法

最终版本

  1. vector<int> pre[maxn];
  2. void Dijkstra(int s){
  3.     fill(d, d + maxn, inf);
  4.     d[s] = 0
  5.     for(int i = 0; i < n; i++){
  6.         int u = -1, min = inf;
  7.         for(int j = 0; j < n; j++){
  8.             if(vis[j] == false && d[j] < min){
  9.                 u = j;
  10.                 min = d[j];
  11.             }
  12.         }
  13.         if(u == -1) return;
  14.         vis[u] = true;
  15.         for(int v = 0; v < n; v++){
  16.             if(vis[v] == false && G[u][v] != inf){
  17.                 if(G[u][v] + d[u] < d[v]){
  18.                     pre[v].clear();
  19.                     pre[v].push_back(u);
  20.                     d[v] = d[u] + G[u][v];
  21.                 } else if(d[v] == d[u] + G[u][v]){
  22.                     pre[v].push_back(u);
  23.                 }
  24.             }
  25.         }
  26.     }
  27. }

伪代码

  1. Dijkstra(G, d[], s){
  2.     for(循环n次){
  3.         u = 使d[u]最小的还未访问的顶点的标号;
  4.         记u已经被访问;
  5.         for(从u出发能到达的所有顶点v){
  6.             if(v未被访问 && 以u为中介点使s到顶点v的最短距离d[v]最优){
  7.                 优化d[v];
  8.             } 
  9.         }
  10.     }
  11. }

邻接矩阵版

  1. const int maxn = 1000;
  2. const int INF = 0x3fffffff;
  4. int n, G[maxn][maxn];
  5. int d[maxn];
  6. bool vis[maxn] = {false};
  8. void Dijkstra(int s){
  9.     fill(d, d + maxn, INF);
  10.     d[s] = 0;
  11.     for(int i = 0; i < n;i ++){
  12.         //找到未被访问中最小的d[u]
  13.         int u = -1, min = INF;
  14.         for(int j = 0; j < n; j++){
  15.             if(vis[j] == false && d[j] < min){
  16.                 u = j;
  17.                 min = d[j];
  18.             }
  19.         }
  20.         if(u == -1) return;//剩下的都不连通
  21.         vis[u] = true;
  22.         //更新距离
  23.         for(int v = 0; v < n; v++){
  24.             if(vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]){
  25.                 d[v] = d[u] + G[u][v];
  26.             }
  27.         }
  28.     }
  29. }

邻接表版

  1. struct Node{
  2.     int v, dis;
  3. };
  4. vector<Node> Adj[maxn];
  5. int n;
  6. int d[maxn];//到达各点的最小路径长度
  7. bool vis[maxn] = {false};
  9. void Dijkstra(int s){
  10.     fill(d, d + maxn, INF);
  11.     d[s] = 0;
  12.     //找距离最小的
  13.     for(int i = 0; i < n; i++){
  14.         int u = -1, min = INF;
  15.         for(int j = 0; j < n; j++){
  16.             if(vis[j] == false && d[j] < min){
  17.                 u = j;
  18.                 min = d[j];
  19.             }
  20.         }
  21.     }
  22.     if(u == -1) return;
  23.     vis[u] = true;
  24.     //只有这部分不同
  25.     for(int j = 0; j < Adj[u].size(); j++){
  26.         int v = Adj[u][j].v;
  27.         if(vis[v] == false && d[u] + Adj[u][j].dis < d[v]){
  28.             d[v] = d[u] + Adj[u][j];
  29.         }
  30.     }
  31. }