Leetcode 1514. Path with Maximum Probability (python)_综合

题目

在这里插入图片描述

解法：bellman ford

这个题目本质上还是个图中求最短路径的问题
参考leetcode Path With Minimum Effort解法

class Solution:def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:graph = collections.defaultdict(list)for edge in edges:graph[edge[0]].append(edge[1])graph[edge[1]].append(edge[0])edge2prob = {
    }for i,edge in enumerate(edges):edge2prob[(edge[0],edge[1])] = succProb[i]edge2prob[(edge[1],edge[0])] = succProb[i]q = collections.deque()q.append((start,1))prob_vec = [0]*n#ans = 0while q:node,prob = q.popleft()for nei in graph[node]:new_prob = edge2prob[(nei,node)]*probif new_prob>prob_vec[nei]:q.append((nei,new_prob))prob_vec[nei] = new_probreturn prob_vec[end]

解法2：Dijkstra

class Solution:def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:graph = collections.defaultdict(list)for edge in edges:graph[edge[0]].append(edge[1])graph[edge[1]].append(edge[0])edge2prob = {
    }for i,edge in enumerate(edges):edge2prob[(edge[0],edge[1])] = succProb[i]edge2prob[(edge[1],edge[0])] = succProb[i]#q = collections.deque()q = [(-1,start)]prob_vec = [0]*n#ans = 0while q:prob,node = heapq.heappop(q)#print(prob,node)if node==end:return -probfor nei in graph[node]:new_prob = edge2prob[(nei,node)]*(-prob)if new_prob>prob_vec[nei]:heapq.heappush(q,(-new_prob,nei))prob_vec[nei] = new_probreturn prob_vec[end]

解法3：log+bellman ford

实际上概率相乘会出现精度问题的，所以转换为log之后做加法更精确。虽然这道题做乘法也可以过

class Solution:def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:graph = collections.defaultdict(list)for edge in edges:graph[edge[0]].append(edge[1])graph[edge[1]].append(edge[0])# change it to log scalefor i in range(len(succProb)):succProb[i] = math.log(succProb[i])edge2prob = {
    }for i,edge in enumerate(edges):edge2prob[(edge[0],edge[1])] = succProb[i]edge2prob[(edge[1],edge[0])] = succProb[i]q = collections.deque()q.append((start,0))prob_vec = [float('-inf')]*n#ans = 0while q:node,prob = q.popleft()for nei in graph[node]:new_prob = edge2prob[(nei,node)]+probif new_prob>prob_vec[nei]:q.append((nei,new_prob))prob_vec[nei] = new_probreturn math.exp(prob_vec[end])

二刷

二刷的时候一开始写bellmanford，memory超了，因为分别存了n*n的dists和adj矩阵，还存了一个graph

class Solution {
    
public:double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
    vector<vector<double>> dists(n,vector<double>(n,0));vector<vector<double>> adj(n,vector<double>(n,0));adj[start][start] = 1;dists[start][start] = 1;vector<vector<int>> g(n,vector<int>());for(int i=0;i<edges.size();i++){
    g[edges[i][0]].push_back(edges[i][1]);g[edges[i][1]].push_back(edges[i][0]);adj[edges[i][0]][edges[i][1]] = succProb[i];adj[edges[i][1]][edges[i][0]] = succProb[i];}// cout << adj[1][2] << endl;queue<int> q;q.push(start);while(!q.empty()){
    int currNode = q.front();q.pop();double currProb = dists[start][currNode];// int currNode = curr.second;// cout << currNode << " " << currProb << endl;for(auto& neigh : g[currNode]){
    double neighProb = adj[neigh][currNode];// cout << currNode << " " << " " << neigh << " " << neighProb << endl;if(neighProb * currProb > dists[start][neigh]){
    q.push(neigh);dists[start][neigh] = neighProb * currProb;}}}return dists[start][end];}
};

所以做了下面的两个改进：

由于开始的start是固定的，所以无需二维矩阵，直接一维向量就可以储存
去掉adj矩阵，直接在构建图的时候放入边的概率

class Solution {
    
public:double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
    vector<double> dists(n,0);dists[start] = 1;vector<vector<pair<int,double>>> g(n);for(int i=0;i<edges.size();i++){
    g[edges[i][0]].push_back(make_pair(edges[i][1],succProb[i]));g[edges[i][1]].push_back(make_pair(edges[i][0],succProb[i]));}// cout << adj[1][2] << endl; queue<int> q;q.push(start);while(!q.empty()){
    int currNode = q.front();q.pop();double currProb = dists[currNode];for(auto& neigh : g[currNode]){
    double neighProb = neigh.second;if(neighProb * currProb > dists[neigh.first]){
    q.push(neigh.first);dists[neigh.first] = neighProb * currProb;}}}return dists[end];}
};

最后利用heap来写dijkstra

class Solution {
    
public:double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
    vector<double> dists(n,0);dists[start] = 1;vector<vector<pair<int,double>>> g(n);for(int i=0;i<edges.size();i++){
    g[edges[i][0]].push_back(make_pair(edges[i][1],succProb[i]));g[edges[i][1]].push_back(make_pair(edges[i][0],succProb[i]));}// cout << adj[1][2] << endl;priority_queue<pair<int,double>> q;q.push(make_pair(start,1));while(!q.empty()){
    pair<int,double> curr = q.top();q.pop();double currProb = curr.second;int currNode = curr.first;for(auto& neigh : g[currNode]){
    double neighProb = neigh.second;if(neighProb * currProb > dists[neigh.first]){
    q.push(make_pair(neigh.first,neighProb * currProb));dists[neigh.first] = neighProb * currProb;}}}return dists[end];}
};

时间复杂度：bellmanford时间复杂度是O(V*E),也就是O(V^3), dijkstra是O(log(V)*E)
空间复杂度：对于上面这种空间最优的解法是O(V)，来源于graph的创建