写在前面

Dijkstra 算法实质上就是 BFS 算法的加强版，算法的模拟过程就是BFS，只不过 Dijkstra 算法一般来说是有固定的起止位置的，然后计算这两点之间的最大或者最小路径或者其他“权重”（例如1631. 最小体力消耗路径 中的高度差）。也就是说Dijkstra计算的是对图中的一条路径进行最优计算，而前面的 Kruskal和Prim算法都是对整个图的最优计算（最小生成树权重）。 Dijkstra 计算最短路径的正确性依赖一个前提：路径中每增加一条边，路径的总权重就会增加，反之也可以；有时候也可以不是最短或者最长。就是计算一条最优路径也是可以的，根据情况而定。

优先队列（贪心）

  • 优先队列辅助计算，它的作用就是贪心，它能保证你第一次到达end的结果就是题目要求的。队列中元素一定包含两个信息：位置及状态值，所谓状态值就是和题目所求相关的变量，可以用pair对保存，也可以用class类保存.
  • 另外优先队列的排序方法应该根据题目来定，如果是计算最小相关则应该使用最小堆，反之则使用最大堆。

距离数组（最优权重）

  • 距离数组的初始化：这个要特别注意，应该设置为较大的值还是较小的值，根据题目而定，因为这涉及到BFS的更新过程。

最优权重更新机制

  • 另外就是，注意dist数组（dist中的值都是起始位置到node的最优值）的更新机制，以本题最大概率为例，假设当前到达节点为n1,n1的邻接点有n2，则dist[n2]的更新机制应该是过往的dist[n2]结果小于dist[n1]与n1到n2的综合结果（也就是$dist[n1]*prob(n1,n2)$）；再比如1631. 最小体力消耗路径，对应的更新机制应该是dist[n2]与综合结果（$max(dist[n1],height(n1,n2))$），也从侧面说明了Dijkstra 算法解决的最优是多方面，不一定最短或者最长，也有可能是其他权重。

visited数组？

  • 会不会走回头路？感觉不会，因为走回头路只会增加相应的权重，而且只有能够更新dist[n]时才会将可能最优路径加入队列。

Dijkstra算法

以1631. 最小体力消耗路径 为例

class state {
public:
    state(int node,double prob){
        this->node=node;
        this->prob=prob;
    }
    int node;
    double prob;
};
class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& su＊＊＊rob, int start, int end) {
        vector<vector<pair<int,double>>> graph=buildGraph(n,edges,su＊＊＊rob);
        vector<double> dist(n,-1);
        dist[start]=0.0;   // start2start设置为零
        // BFS优先队列
        auto cmp=[](const state&s1,const state&s2){return s1.prob < s2.prob;};
        priority_queue<state,vector<state>,decltype(cmp)> Q(cmp);
        for(auto s:graph[start]) {
            int ed=s.first;
            double prob=s.second;
            dist[ed]=prob;
            Q.push(state(ed,prob));
        }
        while(!Q.empty()) {
            state cur=Q.top();
            Q.pop();
            int ed=cur.node;
            double prob=cur.prob;
            if(ed==end)
                return dist[ed];
            if(dist[ed]>prob) continue;
            // 更新概率值
            dist[ed]=prob;
            for(auto s:graph[ed]){
                int nod=s.first;
                double prob=s.second;
                if(dist[nod]<dist[ed]*prob){
                    dist[nod]=dist[ed]*prob;
                    Q.push(state(nod,dist[nod]));
                }
            }
        }
        return 0;
    }
    // 有向无向不重要？
    vector<vector<pair<int,double>>> buildGraph(int n,vector<vector<int>>& edges, vector<double>& su＊＊＊rob) {
        vector<vector<pair<int,double>>> graph(n);
        for(int i=0;i<edges.size();i++){
            // 起始位置
            int start=edges[i][0],end=edges[i][1];
            // 到达最大概率
            double prob=su＊＊＊rob[i];
            graph[start].push_back(make_pair(end,prob));
            graph[end].push_back(make_pair(start,prob));
        }
        return graph;
    }
};

$\cdots$ end $\cdots$