{"id":7079,"date":"2020-07-11T22:44:28","date_gmt":"2020-07-12T05:44:28","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7079"},"modified":"2020-07-12T00:06:14","modified_gmt":"2020-07-12T07:06:14","slug":"leetcode-1514-path-with-maximum-probability","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1514-path-with-maximum-probability\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1514. Path with Maximum Probability"},"content":{"rendered":"\n

You are given an undirected weighted graph of n<\/code> nodes (0-indexed), represented by an edge list where edges[i] = [a, b]<\/code> is an undirected edge connecting the nodes a<\/code> and b<\/code> with a probability of success of traversing that edge succProb[i]<\/code>.<\/p>\n\n\n\n

Given two nodes start<\/code> and end<\/code>, find the path with the maximum probability of success to go from start<\/code> to end<\/code> and return its success probability.<\/p>\n\n\n\n

If there is no path from start<\/code> to end<\/code>, return 0<\/strong>. Your answer will be accepted if it differs from the correct answer by at most 1e-5<\/strong>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2\nOutput:<\/strong> 0.25000\nExplanation:<\/strong> There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2\nOutput:<\/strong> 0.30000\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2\nOutput:<\/strong> 0.00000\nExplanation:<\/strong> There is no path between 0 and 2.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 2 <= n <= 10^4<\/code><\/li>
  • 0 <= start, end < n<\/code><\/li>
  • start != end<\/code><\/li>
  • 0 <= a, b < n<\/code><\/li>
  • a != b<\/code><\/li>
  • 0 <= succProb.length == edges.length <= 2*10^4<\/code><\/li>
  • 0 <= succProb[i] <= 1<\/code><\/li>
  • There is at most one edge between every two nodes.<\/li><\/ul>\n\n\n\n
    Solution: Dijkstra’s Algorithm<\/strong><\/h2>\n\n\n\n
    max(P1*P2*…*Pn) => max(log(P1*P2…*Pn)) => max(log(P1) + log(P2) + … + log(Pn) => min(-(log(P1) + log(P2) … + log(Pn)).<\/p>\n\n\n\n
    Thus we can convert this problem to the classic single source shortest path problem that can be solved with Dijkstra’s algorithm.<\/p>\n\n\n\n
    Time complexity: O(ElogV)
    Space complexity: O(E+V)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  double maxProbability(int n, vector>& edges, \n                        vector& succProb, int start, int end) {\n    vector>> g(n); \/\/ u -> {v, -log(w)}\n    for (int i = 0; i < edges.size(); ++i) {\n      const double w = -log(succProb[i]);\n      g[edges[i][0]].emplace_back(edges[i][1], w);\n      g[edges[i][1]].emplace_back(edges[i][0], w);\n    }\n\n    vector dist(n, FLT_MAX);\n    priority_queue> q;\n    q.emplace(-0.0, start);\n    vector seen(n);\n    while (!q.empty()) {\n      const double d = -q.top().first;\n      const int u = q.top().second;        \n      q.pop();\n      seen[u] = 1;\n      if (u == end) return exp(-d);\n      for (const auto& [v, w] : g[u]) {\n        if (seen[v] || d + w > dist[v]) continue;\n        q.emplace(-(dist[v] = d + w), v);\n      }\n    }\n    return 0;\n  }\n};\n<\/pre>\n\n<\/div>
    Java<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nimport java.util.AbstractMap;\n\nclass Solution {\n  public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {\n    var g = new ArrayList>>();\n    for (int i = 0; i < n; ++i) g.add(new ArrayList>());\n    for (int i = 0; i < edges.length; ++i) {\n      g.get(edges[i][0]).add(new AbstractMap.SimpleEntry<>(edges[i][1], -Math.log(succProb[i])));\n      g.get(edges[i][1]).add(new AbstractMap.SimpleEntry<>(edges[i][0], -Math.log(succProb[i])));\n    }    \n    var seen = new boolean[n];\n    var dist = new double[n];\n    Arrays.fill(dist, Double.MAX_VALUE);\n    seen[start] = true;\n    dist[start] = 0.0;\n    \/\/ {u, dist[u]}\n    var q = new PriorityQueue>(Map.Entry.comparingByValue());    \n    q.offer(new AbstractMap.SimpleEntry<>(start, 0.0));\n    while (!q.isEmpty()) {\n      var node = q.poll();\n      final int u = node.getKey();\n      if (u == end) return Math.exp(-dist[end]);\n      seen[u] = true;\n      for (var e : g.get(u)) {\n        final int v = e.getKey();\n        final double w = e.getValue();\n        if (seen[v] || dist[u] + w > dist[v]) continue;\n        dist[v] = dist[u] + w;\n        q.offer(new AbstractMap.SimpleEntry<>(v, dist[v]));\n      }\n    }\n    return 0;\n  }\n}\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \n# Author: Huahua\nclass Solution:\n  def maxProbability(self, n: int, edges: List[List[int]], \n                     succProb: List[float], start: int, end: int) -> float:\n    g = [[] for _ in range(n)]\n    for i, e in enumerate(edges):\n      g[e[0]].append((e[1], -math.log(succProb[i])))\n      g[e[1]].append((e[0], -math.log(succProb[i])))\n    seen = [False] * n\n    dist = [float('inf')] * n\n    dist[start] = 0.0\n    q = [(dist[start], start)]\n    while q:\n      _, u = heapq.heappop(q)\n      if seen[u]: continue\n      seen[u] = True\n      if u == end: return math.exp(-dist[u])\n      for v, w in g[u]:\n        if seen[v] or dist[u] + w > dist[v]: continue\n        dist[v] = dist[u] + w        \n        heapq.heappush(q, (dist[v], v))\n    return 0\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[540,77,177,87],"class_list":["post-7079","post","type-post","status-publish","format-standard","hentry","category-graph","tag-dijkstra","tag-graph","tag-medium","tag-shortest-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7079","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7079"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7079\/revisions"}],"predecessor-version":[{"id":7087,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7079\/revisions\/7087"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7079"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7079"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7079"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}