最短路各种算法步骤、原理及模板（c++）—更新中

dijkstra

速览：在联通带权图中寻找顶点a到顶点z的最短路径的长度。边 ( i , j ) (i, j) (i,j)的权值 w ( i , j ) > 0 w(i,j)>0 w(i,j)>0，且顶点的标注为 L ( x ) L(x) L(x)，结束时， L ( z ) L(z) L(z)是从 a a a到 z z z的最短路径的长度。

找视频学习基本步骤

伪代码

dijkstra(w,a,z,L){
  L(a)=0
  for all vertices x!=a
    L(x)=inf
  T=set of all vertices   // 临时标注的顶点集合，从a到有最短路径的顶点集合
  // 没找到
  while(z属于T){
    choose v属于T with minimum L(v)
    T=T-{v}
    for each x属于T adjacent to v
      L(x)=min{L(x),L(v)+w(v,x)}
  }
}

证明

邻接矩阵暴力搜索版

void dijkstra_AdjMatrix(){
    for (int i = 0; i < maxn; i++){
        dis[i] = 0x1f1f1f1f;    // 初始化到i点的最短路
    }
    memset(vis, 0, sizeof vis);
    dis[1] = 0;                 // 到起始点的距离，可以改为起始点下标
    for (int i = 1; i<n; i++){
        int x = 0;              // 当前dis最小的点
        for (int j = 1; j <= n; j++){
            if(!vis[j] && (x==0 || dis[j]<dis[x]))      // 在T集合中，且自起始点路长最短
                x = j;
        }
        vis[x] = 1;             // 该点被从T集合中剔除
        for (int j = 1; j<=n; j++){
            dis[j] = min(dis[j], dis[x] + AdjMatrix[x][j]);
                                // 松弛操作 L(x)=min{L(x),L(v)+w(v,x)}
        }
    }
}

优先队列+邻接表

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
const int maxn = 1e4 + 7;
const int tempp = (1 << 31) - 1;    // 注意左移符号优先级低于+-号
const int INF = 2147483647;
int n = 0;
// n为点的数目，m为边的数目
// Dijkstra
// 单源最短路
// 邻接表
// 优先队列
// 边权非负
// O(mlog(m))

struct edge {                       // 边
  int v, w;
};
struct node {                       // 加入优先队列的节点
  int dis, u;
  bool operator>(const node& a) const { return dis > a.dis; }
                // 重载运算符，用于实现优先队列参数
};
vector<edge> e[maxn];               // vector邻接表
int dis[maxn], vis[maxn];           
            // dis为出发点到i节点最短距离，vis为是否松弛了该节点
priority_queue<node, vector<node>, greater<node> > q;

void dijkstra(int n, int s) {
    for (int i = 0; i < maxn; i++){
        dis[i] = INF;
    }
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
}

signed main(){
    int m;
    int s;
    cin >> n >> m >> s;         // 节点数，边数，起始节点编号
    int a, b, diss;
    for (int i = 0; i < m; i++){
        cin >> a >> b >> diss;
        edge temp;
        temp.v = b;
        temp.w = diss;
        e[a].push_back(temp);
    }
    dijkstra(n, s);
    for (int i = 1; i <= n; i++){
        cout << dis[i] << " ";
    }
    return 0;
}