Leetcode 1514. 概率最大的路径

1.题目基本信息

1.1.题目描述

给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。

指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。

如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。

1.2.题目地址

https://leetcode.cn/problems/path-with-maximum-probability/description/

2.解题方法

2.1.解题思路

Dijkstra算法+优先队列优化

2.2.解题步骤

第一步，构建邻接表

第二步，通过Dijkstra算法算出单源最长路径，将路径相加变成路径相乘

第三步，返回end_node的但源最长路径

3.解题代码

Python代码

from typing import List
import heapq
inf=float("inf")
# dijkstra最大路径模板
def dijkstraMaxDist(graph:List[List[List]],startNode:int):
    length=len(graph)
    dists=[0]*length  # *各个节点到startNode的最大概率
    dists[startNode]=1  # *初始化startNode到startNode的最大概率
    pathsPrevs=[-1]*length      # 最短路径的最后节点的前驱节点
    distsHeap=[[-1,startNode]]   # *距离优先队列，项的结构为[距离startNode的距离,node]，需要构建最大堆，将权值取负
    while distsHeap:
        dist,node=heapq.heappop(distsHeap)
        dist=-dist
        if dist<dists[node]:    # *排除同一个
            continue
        for edgeWeight,subNode in graph[node]:
            thisDist=edgeWeight*dists[node]
            if thisDist>dists[subNode]: # *
                dists[subNode]=thisDist
                pathsPrevs[subNode]=node
                heapq.heappush(distsHeap,[-thisDist,subNode])    # *
    return dists,pathsPrevs


class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        # 第一步，构建邻接表
        graph=[[] for i in range(n)]
        for i,edge in enumerate(edges):
            graph[edge[0]].append([succProb[i],edge[1]])
            graph[edge[1]].append([succProb[i],edge[0]])
        # 第二步，通过Dijkstra算法算出单源最长路径，将路径相加变成路径相乘
        probs,pathsPrevs=dijkstraMaxDist(graph,start_node)
        # print(probs,pathsPrevs)
        # 第三步，返回end_node的但源最长路径
        return probs[end_node]

C++代码

class Solution {
public:
    vector<double> dijkstraMaxDist(vector<vector<pair<double,int>>>& graph,int startNode){
        int length=graph.size();
        vector<double> dists(length,0);
        dists[startNode]=1;
        // vector<int> pathsPrevs(length,-1);
        priority_queue<pair<double,int>> distsHeap;
        distsHeap.emplace(1,startNode);
        while(!distsHeap.empty()){
            auto item=distsHeap.top();
            double dist=item.first;
            int node=item.second;
            distsHeap.pop();
            if(dist<dists[node]){
                continue;
            }
            for(int i=0;i<graph[node].size();++i){
                auto item1=graph[node][i];
                double edgeWeight=item1.first;
                int subNode=item1.second;
                double thisDist=edgeWeight*dists[node];
                if(thisDist>dists[subNode]){
                    dists[subNode]=thisDist;
                    // pathsPrevs[subNode]=node;
                    distsHeap.emplace(thisDist,subNode);
                }
            }
        }
        return dists;
    }

    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
        vector<vector<pair<double,int>>> graph(n);
        for(int i=0;i<edges.size();++i){
            auto& edge = edges[i];
            graph[edge[0]].emplace_back(succProb[i],edge[1]);
            graph[edge[1]].emplace_back(succProb[i],edge[0]);
        }
        // for(auto i:graph){
        //     for(auto j:i){
        //         cout << j.first << " " << j.second << endl;
        //     }
        //     cout << endl;
        // }
        vector<double> probs=dijkstraMaxDist(graph,start_node);
        return probs[end_node];
    }
};

4.执行结果