{"id":10015,"date":"2023-04-29T12:16:35","date_gmt":"2023-04-29T19:16:35","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=10015"},"modified":"2023-04-29T12:33:18","modified_gmt":"2023-04-29T19:33:18","slug":"leetcode-2642-design-graph-with-shortest-path-calculator","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-2642-design-graph-with-shortest-path-calculator\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2642. Design Graph With Shortest Path Calculator"},"content":{"rendered":"\n<p>There is a&nbsp;<strong>directed weighted<\/strong>&nbsp;graph that consists of&nbsp;<code>n<\/code>&nbsp;nodes numbered from&nbsp;<code>0<\/code>&nbsp;to&nbsp;<code>n - 1<\/code>. The edges of the graph are initially represented by the given array&nbsp;<code>edges<\/code>&nbsp;where&nbsp;<code>edges[i] = [from<sub>i<\/sub>, to<sub>i<\/sub>, edgeCost<sub>i<\/sub>]<\/code>&nbsp;meaning that there is an edge from&nbsp;<code>from<sub>i<\/sub><\/code>&nbsp;to&nbsp;<code>to<sub>i<\/sub><\/code>&nbsp;with the cost&nbsp;<code>edgeCost<sub>i<\/sub><\/code>.<\/p>\n\n\n\n<p>Implement the&nbsp;<code>Graph<\/code>&nbsp;class:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>Graph(int n, int[][] edges)<\/code>&nbsp;initializes the object with&nbsp;<code>n<\/code>&nbsp;nodes and the given edges.<\/li><li><code>addEdge(int[] edge)<\/code>&nbsp;adds an edge to the list of edges where&nbsp;<code>edge = [from, to, edgeCost]<\/code>. It is guaranteed that there is no edge between the two nodes before adding this one.<\/li><li><code>int shortestPath(int node1, int node2)<\/code>&nbsp;returns the&nbsp;<strong>minimum<\/strong>&nbsp;cost of a path from&nbsp;<code>node1<\/code>&nbsp;to&nbsp;<code>node2<\/code>. If no path exists, return&nbsp;<code>-1<\/code>. The cost of a path is the sum of the costs of the edges in the path.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2023\/01\/11\/graph3drawio-2.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input<\/strong>\n[\"Graph\", \"shortestPath\", \"shortestPath\", \"addEdge\", \"shortestPath\"]\n[[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]]\n<strong>Output<\/strong>\n[null, 6, -1, null, 6]\n<\/pre>\n\n\n\n<p><strong>Explanation<\/strong> <\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]); g.shortestPath(3, 2); \/\/ return 6. The shortest path from 3 to 2 in the first diagram above is 3 -> 0 -> 1 -> 2 with a total cost of 3 + 2 + 1 = 6.\ng.shortestPath(0, 3); \/\/ return -1. There is no path from 0 to 3. \ng.addEdge([1, 3, 4]); \/\/ We add an edge from node 1 to node 3, and we get the second diagram above. \ng.shortestPath(0, 3); \/\/ return 6. The shortest path from 0 to 3 now is 0 -> 1 -> 3 with a total cost of 2 + 4 = 6.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= n &lt;= 100<\/code><\/li><li><code>0 &lt;= edges.length &lt;= n * (n - 1)<\/code><\/li><li><code>edges[i].length == edge.length == 3<\/code><\/li><li><code>0 &lt;= from<sub>i<\/sub>, to<sub>i<\/sub>, from, to, node1, node2 &lt;= n - 1<\/code><\/li><li><code>1 &lt;= edgeCost<sub>i<\/sub>, edgeCost &lt;= 10<sup>6<\/sup><\/code><\/li><li>There are no repeated edges and no self-loops in the graph at any point.<\/li><li>At most&nbsp;<code>100<\/code>&nbsp;calls will be made for&nbsp;<code>addEdge<\/code>.<\/li><li>At most&nbsp;<code>100<\/code>&nbsp;calls will be made for&nbsp;<code>shortestPath<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Floyd-Washall<\/strong><\/h2>\n\n\n\n<p>Time complexity:<br>Init O(n<sup>3<\/sup>)<br>addEdge O(n<sup>2<\/sup>)<br>shortestPath O(1)<\/p>\n\n\n\n<p>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Graph {\npublic:\n  Graph(int n, vector<vector<int>>& edges):\n  n_(n),\n  d_(n, vector<long>(n, 1e18)) {\n    for (int i = 0; i < n; ++i)\n      d_[i][i] = 0;\n    for (const vector<int>& e : edges)\n      d_[e[0]][e[1]] = e[2];    \n    for (int k = 0; k < n; ++k)\n      for (int i = 0; i < n; ++i)\n        for (int j = 0; j < n; ++j)\n          d_[i][j] = min(d_[i][j], d_[i][k] + d_[k][j]);\n  }\n  \n  void addEdge(vector<int> edge) {    \n    for (int i = 0; i < n_; ++i)\n      for (int j = 0; j < n_; ++j)\n        d_[i][j] = min(d_[i][j], d_[i][edge[0]] + edge[2] + d_[edge[1]][j]);\n  }\n  \n  int shortestPath(int node1, int node2) {\n    return d_[node1][node2] >= 1e18 ? -1 : d_[node1][node2];\n  }\nprivate:\n  int n_;\n  vector<vector<long>> d_;\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Dijkstra<\/strong><\/h2>\n\n\n\n<p>Time complexity: <br>Init: O(|E|) ~ O(n<sup>2<\/sup>)<br>AddEdge: O(1)<br>ShortestPath: O(|V|*log(|E|)) ~ O(n*logn)<\/p>\n\n\n\n<p>Space complexity: O(E|) ~ O(n<sup>2<\/sup>)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Graph {\npublic:\n    Graph(int n, vector<vector<int>>& edges): n_(n), g_(n) {\n      for (const auto& e : edges)\n        g_[e[0]].emplace_back(e[1], e[2]);\n    }\n    \n    void addEdge(vector<int> edge) {\n      g_[edge[0]].emplace_back(edge[1], edge[2]);\n    }\n    \n    int shortestPath(int node1, int node2) {\n      vector<int> dist(n_, INT_MAX);\n      dist[node1] = 0;\n      priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;\n      q.emplace(0, node1);\n      while (!q.empty()) {\n        const auto [d, u] = q.top(); q.pop();        \n        if (u == node2) return d;\n        for (const auto& [v, c] : g_[u])\n          if (dist[u] + c < dist[v]) {\n            dist[v] = dist[u] + c;\n            q.emplace(dist[v], v);\n          }\n      }\n      return -1;\n    }\nprivate:\n  int n_;\n  vector<vector<pair<int, int>>> g_;\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There is a&nbsp;directed weighted&nbsp;graph that consists of&nbsp;n&nbsp;nodes numbered from&nbsp;0&nbsp;to&nbsp;n &#8211; 1. The edges of the graph are initially represented by the given array&nbsp;edges&nbsp;where&nbsp;edges[i] = [fromi,&#8230;<\/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,538,77,217,87],"class_list":["post-10015","post","type-post","status-publish","format-standard","hentry","category-graph","tag-dijkstra","tag-floyd-warshall","tag-graph","tag-hard","tag-shortest-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10015","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=10015"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10015\/revisions"}],"predecessor-version":[{"id":10021,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10015\/revisions\/10021"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=10015"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=10015"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=10015"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}