O(V+E)与O(E*logV)复杂度对比及Leetcode最大概率路径算法疑问

我在解决LeetCode的「路径的最大概率」问题时，用简单BFS写出了能通过测试的解法，但发现大家普遍使用Dijkstra算法。我想知道Dijkstra的时间复杂度是否更优，或是选择该算法存在其他逻辑。

我的解法代码如下：

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<pair<int,double>> adj[n];
        for(int i=0;i<edges.size();i++){
            adj[edges[i][0]].push_back({edges[i][1],succProb[i]});
            adj[edges[i][1]].push_back({edges[i][0],succProb[i]});
        }
        queue<int> q;
        q.push(start);
        vector<double> dist(n,0.0);
        dist[start]=1;
        while(!q.empty()){
            auto temp=q.front();
            q.pop();
            for(auto it:adj[temp]){
               
               int node=it.first;
               double prob=it.second;
               double newprob=dist[temp]*prob;
                if(newprob>dist[node]){
                    dist[node]=newprob;
                    q.push(node);
                }
                
            }
        }
        return dist[end];
    }
};

问题解答 #

• 你的BFS解法的本质与局限
  你的BFS实现其实是对Bellman-Ford算法的简化，通过队列重复对节点进行松弛操作。但这种方式的问题在于：同一个节点可能被多次加入队列，当图的边数较多时，最坏时间复杂度会达到O(E*V)（E为边数，V为节点数）。虽然小规模测试用例能通过，但面对大规模图时，很容易出现超时。

• Dijkstra算法的时间复杂度优势
  该问题核心是求从起点到终点的最大概率路径，由于所有边的概率都是≤1的正数，路径越长，概率乘积只会越小。这时候Dijkstra算法的贪心策略完全适用：每次选择当前概率最大的节点进行松弛操作，一旦处理到终点就可以提前终止，且每个节点只会被处理一次。
  用二叉堆实现优先队列的Dijkstra算法，时间复杂度为O(E log V)，比你的BFS在最坏情况下高效得多。

• 选择Dijkstra的逻辑适配性
  Dijkstra原本用于求最短路径，这里我们把“距离”替换为“概率乘积”，把“找最小值”换成“找最大值”，完全符合算法的适用条件：不存在负权重（这里所有边的概率都是正的），且一旦找到某个节点的最大概率，后续不可能出现更大的路径来更新它（因为再走任何边都会让乘积变小），所以贪心策略是正确的，无需重复处理节点。

内容的提问来源于stack exchange，提问作者Anshika Agarwal