1 Dijkstra 算法

Dijkstra（迪杰斯特拉）算法适用于单源最短路径问题，即从一个起点出发，计算到所有其他点的最短路径。它只能用于边权非负的图（所有边的权重 ≥ 0），无法解決带负权的图的最短路问题。

Dijkstra 算法的核心思想是贪心算法，将所有节点分为已确定最短路径的节点和未确定最短路径的节点:

1. 初始时，将所有顶点的最短距离设为∞，源点的距离设为0
2. 每次从未确定节点中选择距离最小的节点，作为当前节点，将其标记为已确定
3. 遍历当前节点的所有邻居，更新该节点的所有邻居节点的距离（松弛操作）
4. 重复上述过程，直到所有节点都被加入已确定集合

“松弛”就是检查当前路径是否更短，如果是，就更新最短距离。

• 邻接矩阵+迭代

const int N = 1010;  
int n, m, s, mp[N][N], dis[N];  // 节点 边 起始点 图 距离
bool vis[N];  // 已确定节点

void dij() {  
    fill(dis, dis + N, INT_MAX);  // 未确定节点的距离设为无穷大
    dis[s] = 0;  // 起始节点距离设为0

	// 一次确定一个节点的最短路，n个节点需要n次循环
    for(int i = 1; i <= n; i++) {  
        int id = 0;  // id标记当前节点，初始化为0，距离为无穷大
        for(int j = 1; j <= n; j++)  // 在未确定节点中寻找距离最小的节点
            if (!vis[j] && dis[j] < dis[id]) id = j;  
  
        vis[id] = true;  // 将当前节点标记为已确定
        for (int j = 1; j <= n; j++)  
	        // 松弛，当前节点的邻居，从当前节点出发路径更短
            if (mp[id][j] != INT_MAX && dis[id] + mp[id][j] < dis[j])  
                dis[j] = dis[id] + mp[id][j];  
    }  
}

• 递归实现（数据稍大会栈溢出）

const int N = 1010;  
int n, m, s, mp[N][N], dis[N];  // 节点  边  起始点  图  距离
bool vis[N];  // 已确定节点
  
void dij(int id) {  // 当前节点
    int mini = INT_MAX, ni = -1;  // 未确定节点中的最短距离和节点编号
    vis[id] = true;  // 标记为已确定
    for(int i = 1; i <= n; i++) {  
        if(!vis[i]) {  // 遍历还未确定的节点
	        // 当前节点能访问到的邻居 并且 从当前节点出发的路径更短
            if(mp[id][i] != INT_MAX && dis[id] + mp[id][i] < dis[i])  
                dis[i] = dis[id] + mp[id][i];  // 松弛
            // 在所有还未确定的节点中寻距离最短的
            if(dis[i] < mini) { 
                mini = dis[i];  // 更新最短距离
                ni = i;  // 更新节点编号
            }  
        }    
	}  
	// 如果找到了未确定节点中的最短距离节点，作为当前节点传入dij
	if(ni != -1) dij(ni);  
}  
  
int main() {  
    cin >> n >> m >> s;  
    fill(mp[0], mp[0] + N * N, INT_MAX);  // 边初始化为无穷大
    while(m--) {  
        int u, v, w;  
        cin >> u >> v >> w;  
        mp[u][v] = min(mp[u][v], w);  // 处理重边  
    }  
  
    fill(dis, dis + N, INT_MAX);  //  距离初始化为无穷大
    dis[s] = 0;  //  起始点距离初始化为0
    dij(s);  
  
    for(int i = 1; i <= n; i++)  
        if(dis[i] != INT_MAX) cout << dis[i] << " ";  
        else cout << -1 << " ";
}

2 Bellman-Ford 算法

Bellman-Ford（贝尔曼-福特）算法是用于解决单源最短路径问题的经典算法，它可以处理图中包含负权边的情况，并能检测出图中是否存在负环。

Bellman-Ford算法的核心是“不断松弛边”。对所有边进行 n - 1 次松弛（n为顶点个数），之后再跑一次检测负环。

1. 初始化：将所有顶点的最短距离估计值设为∞，源点的距离设为0
2. 松弛操作：重复 n-1 次松弛，每次遍历所有边，对每条边进行松弛操作
3. 检查负环：再进行一次松弛操作，如果还能更新则说明存在负环

为什么进行 n-1 次松弛，因为进行一次 Bellman-Ford，距离起点一条边的点的最短路确定， 进行两次，距离起点两条边的点的最短路确定， 总共n个点，最短路最多经过 n-1 条边，所以进行 n-1 次松弛即可。

const int N = 1e5 + 10;  
int n, m, s, t, dis[N];  // 节点数 边数 起始点 目标点 距离
struct Edge {  
    int u;  
    int v;  
    int w;  
    Edge(int from, int to, int weight) : u(from), v(to), w(weight) {}  
};  
vector<Edge> egs;   // 使用边集数组进行存储，方便对每一条
  
void bf() {  
	// 除起始点之外的距离设为无穷大
    fill(dis, dis + N, 1e9);  
    dis[s] = 0;  
  
    for(int i = 1; i < n; i++) {  // n-1 次操作，每次确定距离为 i 的节点最短路
        for(int j = 1; j <= m; j++) {  // 每次操作对所有边进行
	        // 当前边的起始点 当前边的到达点 当前边的权值
            int from = egs[j].u, to = egs[j].v, weight = egs[j].w;  
            if(dis[from] + weight < dis[to])  // 松弛操作
                dis[to] = dis[from] + weight;  
        }  
    }}  
  
int main() {  
    cin >> n >> m >> s >> t;  
    egs.emplace_back(0, 0, 0);  // 占位 vector 的 0 号位
    for(int i = 0; i < m; i++) {  
        int x, y, z;  
        cin >> x >> y >> z;  
        // 直接将 Edge(x,y,z) push_back 进 vector
        egs.emplace_back(x, y, z);  
    }  
  
    bf();  
  
    cout << dis[t];  
  
    return 0;  
}

3 SPFA 算法

SPFA（Shortest Path Faster Algorithm）是 Bellman-Ford 算法的队列优化版本，用于求单源最短路径，减少了不必要的冗余运算，同样可以处理存在负权边的情况。

与 Bellman-Ford 每次都遍历所有边不同，SPFA 利用队列优化了 Bellman-Ford 算法中不必要的松弛操作，只对发生了松弛操作的结点的邻接结点进行松弛。

1. 初始化所有节点到起始点的距离为 ∞，源点为 0
2. 将源点入队，并标记为在队列中
3. 当队列不为空时：
   • 取出队首节点作为当前节点，弹出并标记为不在队列中
   • 遍历从当前节点的所有临接边，尝试松弛操作
   • 如果松弛成功，判断这个邻居节点是否在队列中，如果不在则入队
4. 重复以上操作直到队列为空

const int N = 5010;  
int n, m, s, t, dis[N], mp[N][N];  // 节点 边 源点 终点 距离 图 
queue<int> q;  // 辅助队列
bool vis[N];  // 标记节点是否在队列
  
void spfa() {  
	// 除源点外的其他节点距离初始化为无穷大
    fill(dis, dis + N, 1e9);  
    dis[s] = 0;  
  
    q.push(s);  // 源点入队
    vis[s] = true;  // 并把源点标记为在队列
    while(!q.empty()) { 
        int id = q.front(); // 取出队首元素
        q.pop();  
        vis[id] = false;  // 标记为不在队列
        for(int i = 1; i <= n; i++) {
	        // 遍历所有邻居节点
            if(mp[id][i] != 1e9 && dis[id] + mp[id][i] < dis[i]) {  
                dis[i] = dis[id] + mp[id][i];  // 松弛
                // 如果不在队列则入队，并标记为在队列
                if(!vis[i]) { 
                    q.push(i);  
                    vis[i] = true;  
                }  
            }       
        }    
    }
}

SPFA 每轮更新中将“更近一层”的节点的最短路径传递出去，这个过程和 BFS 逐层访问节点的方式有点相似。

4 Floyd 算法