dijkstra(堆优化版)

47. 参加科学大会（第六期模拟笔试）

1.思路

dijkstra 三部曲：

1. 第一步，选源点到哪个节点近且该节点未被访问过
2. 第二步，该最近节点被标记访问过
3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）

之前是通过遍历节点来遍历边，通过两层 for 循环来寻找距离源点最近节点。 这次直接遍历边，且通过堆来对边进行排序，达到直接选择距离源点最近节点。

初始化:

    pq.push({1,0});
    minDist[1]=0;

     将起点（节点1）和它的距离（0）放入优先队列，并更新距离数组。

主循环:

    while(!pq.empty()){
        // ...
    }

     只要优先队列中还有待处理的节点，循环就继续。

选择最近节点:

    pair<int,int> cur=pq.top();pq.pop();
    if(visited[cur.first]) continue;
    visited[cur.first]=true;

pq.top() 弹出距离最小的节点 cur。
if(visited[cur.first]) continue; 一个节点可能被多次加入优先队列（每次找到更短路径时），所以当我们处理它时，如果它已经被标记为 visited，说明它的最短路径早就确定过了，直接跳过即可。
visited[cur.first]=true; 正式标记当前节点的最短路径已经确定。

更新操作:

    for(Edge edge:graph[cur.first]){
        if(!visited[edge.t] && minDist[cur.first]+edge.val<minDist[edge.t]){
            minDist[edge.t]=minDist[cur.first]+edge.val;
            pq.push({edge.t,minDist[edge.t]});
        }
    }

遍历当前节点 cur.first 的所有邻居 edge.t。
minDist[cur.first]+edge.val<minDist[edge.t] 是核心判断，如果通过 cur.first 到达 edge.t 的路径更短，就执行更新。
minDist[edge.t]= ... 更新最短距离。
pq.push(...) 将更新后的距离和节点 edge.t 重新加入优先队列，以便后续可能影响其他节点。

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>
using namespace std;

// 定义一个结构体来表示带权重的边
struct Edge{
    int t,val;
};
// 小顶堆
class cmp{
public:
    bool operator() (pair<int,int>&a,pair<int,int>&b){
        return a.second>b.second;
    }
};

int main(){
    int n,m;cin>>n>>m;
    vector<list<Edge>>graph(n+1);
    vector<bool>visited(n+1,false);     // 记录顶点是否被访问过
    vector<int>minDist(n+1,INT_MAX);    // 存储从源点到每个节点的最短距离
    priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;    // 优先队列中存放 pair<节点，源点到该节点的权值>
    for(int i=0;i<m;i++){
        int s,t,val;cin>>s>>t>>val;
        // s 指向 t，权值为 val
        graph[s].push_back({t,val});
    }
    pq.push({1,0});    // 初始化队列，源点到源点的距离为0，所以初始为0
    minDist[1]=0;      // 起始点到自身的距离为0
    while(!pq.empty()){
        // 1. 第一步，选源点到哪个节点近且该节点未被访问过
        pair<int,int> cur=pq.top();pq.pop();
        if(visited[cur.first]) continue;
        // 2. 第二步，该最近节点被标记访问过
        visited[cur.first]=true;
        // 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）
        for(Edge edge:graph[cur.first]){
            // cur指向的节点edge.t，这条边的权值为 edge.val
            if(!visited[edge.t] && minDist[cur.first]+edge.val<minDist[edge.t]){
                minDist[edge.t]=minDist[cur.first]+edge.val;
                pq.push({edge.t,minDist[edge.t]});
            }
        }
    }
    if(minDist[n]==INT_MAX) cout<<-1<<endl;
    else cout<<minDist[n]<<endl;

    return 0;
}

2.复杂度分析

时间复杂度：O(ElogE) - E 为边的数量

整个队列一定是所有边添加了一次，同时也弹出了一次，所以边添加一次时间复杂度是 O(E)。while (!pq.empty()) 里每次都要弹出一个边来进行操作，在优先级队列（小顶堆）中弹出一个元素的时间复杂度是 O(logE) ，这是堆排序的时间复杂度。

空间复杂度：O(V + E) - V 为节点的数量    

3.思考

堆优化的整体思路和 朴素版 是大体一样的，区别是 堆优化从边的角度出发且利用堆来排序。

Dijkstra 算法：求解带权有向图的单源最短路径问题

每次都从未确定的节点中选出距离源点最近的节点，然后以其为中心进行松弛操作。

利用最小优先队列来高效地获取距离最小的节点，将算法的时间复杂度从朴素实现的 O(V²) 优化到了 O(E log V)（其中V是节点数，E是边数），这对于处理大规模数据至关重要。

4.Reference：dijkstra（堆优化版）精讲 | 代码随想录

---

Bellman_ford 算法

94. 城市间货物运输 I

1.思路

Bellman-Ford 算法的核心思想非常直观：对所有边进行 n-1 轮松弛操作。

松弛操作: 对于一条边 s -> t，如果 minDist [s] + val < minDist [t]，那么就更新 minDist [t]。

为什么是 n-1 轮？

• 在一个不含负权回路的图中，任意两个节点之间的最短路径，最多只会包含 n-1 条边（因为 n 个节点的简单路径最多 n-1 条边，如果超过，必然有环）。
• 因此，通过 n-1 轮松弛，我们可以保证：
  • 第 1 轮后，所有最短路径为 1 条边的节点，其距离被确定。
  • 第 2 轮后，所有最短路径为 2 条边的节点，其距离被确定。
  • 第 n-1 轮后，所有最短路径最多为 n-1 条边的节点，其距离都被确定。

初始化:

    minDist[1]=0;

     将源点（节点1）到自身的距离设为 0，其他所有点的距离保持为 INT_MAX。

主循环 (松弛阶段):

    for(int i=1;i<n;i++){
        for(vector<int>& side:graph){
            // ... 松弛操作 ...
        }
    }

外层循环 for(int i=1; i<n; i++) 控制松弛的轮数，共进行 n-1 轮。
内层循环 for(vector<int>& side:graph) 遍历图中的每一条边。

这里 vector<int>& side:graph 必须要加上 & ，不然会超时。

松弛操作:

    int s=side[0];
    int t=side[1];
    int val=side[2];
    if(minDist[s]!=INT_MAX && minDist[s]+val<minDist[t]){
        minDist[t]=minDist[s]+val;
    }

对于每条边 s -> t：
if(minDist[s]!=INT_MAX ...): 这是一个重要的边界条件。如果起点 s 本身就不可达（距离还是无穷大），那么从 s 出发的边自然也无法用于松弛。
... && minDist[s]+val<minDist[t]: 这是核心的松弛判断。如果通过 s 到达 t 的路径更短，就更新 minDist[t]。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main(){
    int n,m;cin>>n>>m;
    vector<vector<int>>graph;
    vector<int>minDist(n+1,INT_MAX);
    // 将所有边保存起来
    for(int i=0;i<m;i++){
        int s,t,val;cin>>s>>t>>val;
        // s 指向 t，权值为 val
        graph.push_back({s,t,val});
    }
    minDist[1]=0;
    // 对所有边 松弛 n-1 次
    for(int i=1;i<n;i++){
        // 每一次松弛，都是对所有边进行松弛
        for(vector<int>& side:graph){
            int s=side[0];
            int t=side[1];
            int val=side[2];
            // 松弛操作 
            // minDist[from] != INT_MAX 防止从未计算过的节点出发
            if(minDist[s]!=INT_MAX && minDist[s]+val<minDist[t]){
                minDist[t]=minDist[s]+val;
            }
        }
    }
    if(minDist[n]==INT_MAX) cout<<"unconnected"<<endl;
    else cout<<minDist[n]<<endl; 

    return 0;
}

2.复杂度分析

时间复杂度： O(V * E) , V 为节点数量，E 为图中边的数量

空间复杂度： O(V) ，即 minDist 数组所开辟的空间

3.思考

特性	Bellman-Ford	Dijkstra (堆优化版)
核心思想	动态规划，对所有边进行 n-1 轮松弛	贪心，每次选最近节点进行松弛
数据结构	边集数组，简单直接	邻接表 + 优先队列（最小堆）
时间复杂度	O(V * E) (V是节点数，E是边数)	O(E log E)
处理负权边	可以	不可以
检测负权环	可以（需要额外一轮遍历）	不可以

4.Reference：Bellman_ford 算法精讲 | 代码随想录