Dijkstra算法

原理

在图论或者导航的路径规划中，我们经常需要在一个已知地图中寻找或者规划出从起点到终点的最短路径。Dijkstra算法（中文：迪杰斯特拉算法）是用于寻找在非负权重的图中找到从起点出发到图中各个顶点的最短路径的算法。

Dijkstra算法通常可以分为以下几个步骤：

  1. 初始化: 设定所有顶点到起点的距离为无穷大，然后起点 start 到自身的距离为0; 维持一个待访问集合，首先把起点 start 加入这个集合 S。
  2. 找到当前待访问集合离起点最近的顶点: 取出待访问集合 S 中到起点 start 距离最短的顶点 u
  3. 松弛各个邻接点到起点的距离: 访问 u 的每一个邻接点，看通过 u 作为中继点能否使邻接点到达起点的距离缩短，若更短，那么更新邻接点到起点 start 的最短距离。即如果该邻接点未曾加入待访问集合，那么更新它到起点的更短的距离后把这个邻接点加入待访问集合 S。如果该邻接点已经在待访问集合 S 中，那么直接更新集合 S 中这个顶点到起点 start 的距离。
  4. 重复 2 - 3 步直到待访问集合 S 变成空集合：这样即可以找到起点 start 到所有顶点的最短距离。如果我们是只寻找到一个终点 end 的最短距离的话，当 u 为 end 的时候就可以终止算法的执行。

维基百科 提供的伪代码如下：

function Dijkstra(Graph, source):
 
        create vertex set Q

        for each vertex v in Graph:            
           dist[v] ← INFINITY                 
           prev[v] ← UNDEFINED                
           add v to Q                     
        dist[source] ← 0                       
    
        while Q is not empty:
            u ← vertex in Q with min dist[u]   
                                            
            remove u from Q
         
            for each neighbor v of u:           // only v that are still in Q
               alt ← dist[u] + length(u, v)
               if alt < dist[v]:              
                   dist[v] ← alt
                   prev[v] ← u

        return dist[], prev[]

上述伪代码中，prev[]这个数组记录每个顶点的前驱顶点，用于找到最短路径上的每一个顶点。

该伪代码一开始就把所有点都加入待访问集合了，本质上和我们之前的写法是一样的，但是实际操作时我们可以一开始只把起点加入集合，这样在图中顶点数目很多的时候可以节省上述第2步的时间。

值得注意的是，那么从待访问集合 S 中取出的顶点 u 到起点的距离已经是最短的了，因此当我们初始化的时候只把起点加入待访问集合的话，松弛操作 if alt < dist[v]: 这句一方面可以用于判断是否要更新邻接点到起点的距离，同时还可以防止已经从待访问集合 S 中取出的顶点再度加入集合。这样当图中存在环的时候，不至于不停地把一些顶点重复加入集合 S 中，以致于在环困在死循环中。

Dijkstra算法的时间复杂度主要取决我们怎么实现这一句 u ← vertex in Q with min dist[u], 即找到待访问集合中离起点最近的顶点。

例子

举个栗子，以leetcode中的一道题 1514. Path with Maximum Probability为例:

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i]. Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability. If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

这题要求寻找成功概率最大的路径对应的成功概率，本质可以化解为求最短路径。设任意一条路径上n条边的概率为 \(p_i\) , 那么所求为 \(\prod\limits_{i=0}^{n-1}p_i\) , 在数学等价于我们取个负对数求和在取负指数:

\[ \prod\limits_{i=0}^{n}p_i = exp(\sum\limits_{i=0}^{n-1}\log{p_i}) = exp[-\sum\limits_{i=0}^{n-1}(-\log{p_i})] \]

\(p_i \in [0,1]\), \(-\log p_i \in [0, \inf]\), 而且 \(p_i\) 越大，对应的\(-\log p_i\) 越小， 也就是说我们把每条边的概率权重取个负对数作为边的权重后，问题就变成了求图的最短路径了。这时候Dijkstra算法就派上用场了。

首先，最朴素的想法就是用顺序遍历的方法来 找到当前待访问集合离起点最近的顶点:

// cpp code: use linear array to implement Dijkstra's algorithm
class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        
        // reconstruct the undirected graph using adjacent list
        vector<vector<pair<int, double>> > adj(n);
        for(int i = 0; i < edges.size(); i++){
            adj[edges[i][0]].push_back({edges[i][1], -log(succProb[i])});
            adj[edges[i][1]].push_back({edges[i][0], -log(succProb[i])});
        }

        // use array to implement Dijkstra's algorithm (Time: 1664 ms)   
       
        vector<double> dist(n, DBL_MAX);
        vector<bool> expanded(n, false);

        dist[start] = 0;
        
        for(int i = 0; i < n; i++){
            // find node with minimum cost
            int u = -1;
            double MIN = DBL_MAX;
            for(int j = 0; j < n; j++){
                if(expanded[j] == false && dist[j] < MIN){
                    u = j;
                    MIN = dist[j];
                }
            }
            // early stop
            if(u == -1 || u == end) break;
            // expanded node u
            expanded[u] = true;
            for(auto [v, w]: adj[u]){
                if(dist[u] + w < dist[v]){
                    dist[v] = dist[u] + w;
                }
            }
        }
        
        return exp(-dist[end]);
    }
};

在上述代码中，我们使用顺序遍历来查找待访问集合中离起点距离最小的顶点。其中 expnaded[]用于标记顶点是否被取出了待访问集合，便于顺序寻找时排除已访问的顶点。Dijkstra算法的这种实现比较简单，但是时间耗费较多，我在leetcode测试的结果是通过所有测试用例花费了 1664ms。

因此，我们自然就可以想到优化的起脚点，优化查找待访问集合中离起点距离最小的顶点这一步骤。常见的C++实现Dijkstra算法的代码中，经常使用集合容器std::set 或 优先队列std::priority_queue来实现。std::set底层实现是红黑树，可以实现按集合元素自动从小到大排序，而std::priority_queue是用堆来实现的，默认是大顶堆。

因此，如果我们用std::set来实现Dijkstra算法:

// cpp code: use std::set to implement DIjkstra's algorithm
class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        
        // reconstruct the undirected graph using adjacent list
        vector<vector<pair<int, double>> > adj(n);
        for(int i = 0; i < edges.size(); i++){
            adj[edges[i][0]].push_back({edges[i][1], -log(succProb[i])});
            adj[edges[i][1]].push_back({edges[i][0], -log(succProb[i])});
        }
 
        // using set to implement Dijkstra's algorithm  (Time: 190 ms)    
        
       vector<double> dist(n, DBL_MAX);
       dist[start] = 0;
        
       set<pair<double, int> > st;  // {cost, node_id}
       st.insert({dist[start], start});
        
       while(!st.empty()){
           int u = st.begin()->second;
           st.erase(st.begin());
           
           if(u == end) break;
           
           for(auto [v, w]: adj[u]){
               if(dist[u] + w < dist[v]){
                   st.erase({dist[v], v});
                   dist[v] = dist[u] + w;
                   st.insert({dist[v], v});
               }
           }
           
       }

       return exp(-dist[end]); 
    }
};

在这个用std::set的实现中，可以发现基本和维基百科的伪代码一致，因为插入std::set的元素都是复制了一份的，不支持修改std::set中元素的值。所幸std::set支持查找和删除操作，并且它们的时间复杂度并不高。我们每次需要更新已经进入待访问顶点集合中的顶点的距离值时，先查找删除这个顶点，然后插入新距离值的顶点就可以啦！

同时，用c++ STL的优先队列std::priority_queue来实现Dijkstra算法的话，因为它并不支持查找和删除操作，因此，当前访问的顶点的某个邻接点需要更新最短距离的话，我们只有把具有新距离值的顶点插入优先队列，但是并不删除旧的顶点。不过，这样并不影响最后结果的正确性，因为后插入的新距离值的顶点会比旧顶点先取出优先队列，再当旧顶点被取出优先队列时，由于其距离值已经是最优的了，当该顶点作为其他顶点的邻接点被访问时，不会进入if(dist[u] + w < dist[v])中，同时该顶点的邻接点的距离也在先前就被优化了。具体代码实现如下:

// cpp code: use std::priority_queue to implement Dijkstra's algorithm
class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        
        // reconstruct the undirected graph using adjacent list
        vector<vector<pair<int, double>> > adj(n);
        for(int i = 0; i < edges.size(); i++){
            adj[edges[i][0]].push_back({edges[i][1], -log(succProb[i])});
            adj[edges[i][1]].push_back({edges[i][0], -log(succProb[i])});
        }
        
        //  using priority queue to implement Dijkstra's algorithm  (Time: 160 ms)
        
        vector<double> dist(n, DBL_MAX);
        dist[start] = 0.0;
        typedef pair<double, int> pdi;
        priority_queue<pdi, vector<pdi>, greater<pdi> > pq;  // {cost, node_id}
        pq.push({dist[start], start});
        
        while(!pq.empty()){
            int u = pq.top().second;
            pq.pop();
            
            if(u == end) break;
            
            for(auto [v, w]: adj[u]){
                if(dist[u] + w < dist[v]){
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        
        return exp(-dist[end]);
    }
};

基于上述分析，我们知道即使一个进入待访问集合的顶点有好几份copy在集合中，并不会影响我们的最终结果，那么，我们把if(dist[u] + w < dist[v])这个判断条件去掉可以嘛？不管能不能缩短到起点的距离每次都把通过不同中继点的所有可能到起点的距离值都压入优先队列行吗？ 也是就我们把顶点插入优先队列的时候，进行更大规模的冗余的插入操作，不管该顶点的最短距离能不能缩小，通通把它们push进入优先队列的操作可行吗？

当图中没有环的时候是可以的，但是有环存在的时候，没有这个if条件判断，已经进入过优先队列中的顶点会再次进入优先队列中，环的存在会导致环上的顶点无限循环进入其中。因此我们需要设置一个类似于之前顺序查找的expanded[]数组来标记顶点是否被访问过:

/* cpp code: use std::priority_queue and visited[] to implement Dijkstra's algorithm 
             without edge loose condition constraint
*/
class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        
        // reconstruct the undirected graph using adjacent list
        vector<vector<pair<int, double>> > adj(n);
        for(int i = 0; i < edges.size(); i++){
            adj[edges[i][0]].push_back({edges[i][1], -log(succProb[i])});
            adj[edges[i][1]].push_back({edges[i][0], -log(succProb[i])});
        }
 
        /*********************        This is my test, faster than 100% C++ code   *********************/
        
        vector<bool> visited(n, false);
        typedef pair<double, int> pdi;
        priority_queue<pdi, vector<pdi>, greater<pdi> > pq; // {cost, node_id}
        
        pq.push({0, start});
        
        while(!pq.empty()){
            auto [cost, u] = pq.top();
            pq.pop();
            
            if(u == end) return exp(-cost);
            if(visited[u]) continue;
            
            visited[u] = true;   // consider the case that there is a loop in the graph
            
            for(auto [v, w]: adj[u]){
                pq.push({cost+w, v});  // although redundant push operations
            }
        }
        
        return 0.0;
    }
};

好的，那么现在我们知道了使用了visited[]数组来防止掉如图的环中死循环的情况下，我们允许redundant push operations的操作。我们再来看一道leetcode的题目-787. Cheapest Flights Within K Stops:

There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w. Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

这题要求寻找出中继点不超过k个的情况下的起点到终点的最便宜路径，我们以价钱price作为权重的话，其实就是中继点不超过k个的情况下的最短路径问题。

基于我们刚刚的分析，我们采用最后那种有redundant push operations且使用std::priority_queue的方法来实现Dijkstra算法，唯一要注意的是有不能超过k个中继点的约束条件。这个好办，我们给每个顶点增加一个层次的深度属性，具体来说就是起点深度为0，起点的邻接点深度增加1，以此类推，每次进行redundant push operations的时候，push进优先队列的顶点的深度等于当前访问顶点的深度增加1就行了。

代码实现如下:

/* cpp code for leetcode 787. Cheapest Flights Within K Stops */
class Solution {
    typedef tuple<int, int, int> tiii;  // cost, stops, id
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        // reconstruct the graph from edges using adjacent list
        vector<vector<pair<int, int> > > adj(n);
        for(auto edge: flights){
            adj[edge[0]].push_back({edge[1], edge[2]});
        }
        
        priority_queue<tiii, vector<tiii>, greater<tiii> > pq;
        
        pq.emplace(0, 0, src);
        
        while(!pq.empty()){
            auto [cost, stop, u] = pq.top();
            pq.pop();
            
            if(u == dst) return cost;
            if(stop > K) continue;
            
            for(auto [v, w]: adj[u]){
                pq.emplace(cost+w, stop+1, v);
            }
        }
        
        return -1;
    }
};

可以看到这种用不带邻接顶点边松弛的 redundant push operations 的实现，比用std::set来实现Dijkstra算法虽然没有那么贴近于Wikipedia的算法伪代码描述，但是对于写代码的人来说很简洁。你可以思考下，这道题如果用带邻接顶点边松弛的std::priority_queue来实现或者使用std::set怎么实现？ 你会发现会麻烦很多。

OK， 到目前为止，我们求的都是从起点从终点这样“点对点、一对一”的最短路径，不要忘了，Dijkstra算法本来就是可以求出起点到非负权重图中所有顶点的最短距离，也即可以求出“一对多”的最短距离。只不过，我们在求“一对一”的最短路径的时候，当访问到终点的时候提前终止了算法的while循环，这是一种early stop的操作。

参考

赏

一只小可爱