Package g2601_2700.s2642_design_graph_with_shortest_path_calculator

Class Graph

java.lang.Object
g2601_2700.s2642_design_graph_with_shortest_path_calculator.Graph
public class Graph extends Object
2642 - Design Graph With Shortest Path Calculator.<p>Hard</p> <p>There is a <strong>directed weighted</strong> graph that consists of <code>n</code> nodes numbered from <code>0</code> to <code>n - 1</code>. The edges of the graph are initially represented by the given array <code>edges</code> where <code>edges[i] = [from<sub>i</sub>, to<sub>i</sub>, edgeCost<sub>i</sub>]</code> meaning that there is an edge from <code>from<sub>i</sub></code> to <code>to<sub>i</sub></code> with the cost <code>edgeCost<sub>i</sub></code>.</p> <p>Implement the <code>Graph</code> class:</p> <ul> <li><code>Graph(int n, int[][] edges)</code> initializes the object with <code>n</code> nodes and the given edges.</li> <li><code>addEdge(int[] edge)</code> adds an edge to the list of edges where <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> returns the <strong>minimum</strong> cost of a path from <code>node1</code> to <code>node2</code>. If no path exists, return <code>-1</code>. The cost of a path is the sum of the costs of the edges in the path.</li> </ul> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2023/01/11/graph3drawio-2.png" alt="" /></p> <p><strong>Input</strong> [&ldquo;Graph&rdquo;, &ldquo;shortestPath&rdquo;, &ldquo;shortestPath&rdquo;, &ldquo;addEdge&rdquo;, &ldquo;shortestPath&rdquo;] [[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], <a href="1,-3,-4">1, 3, 4</a>, [0, 3]]</p> <p><strong>Output:</strong> [null, 6, -1, null, 6]</p> <p><strong>Explanation:</strong></p> <p>Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]);</p> <p>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.</p> <p>g.shortestPath(0, 3); // return -1. There is no path from 0 to 3.</p> <p>g.addEdge([1, 3, 4]); // We add an edge from node 1 to node 3, and we get the second diagram above.</p> <p>g.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.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= n <= 100</code></li> <li><code>0 <= edges.length <= n * (n - 1)</code></li> <li><code>edges[i].length == edge.length == 3</code></li> <li><code>0 <= from<sub>i</sub>, to<sub>i</sub>, from, to, node1, node2 <= n - 1</code></li> <li><code>1 <= edgeCost<sub>i</sub>, edgeCost <= 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 <code>100</code> calls will be made for <code>addEdge</code>.</li> <li>At most <code>100</code> calls will be made for <code>shortestPath</code>.</li> </ul>

  • Constructor Details

    • Graph

      public Graph(int n, int[][] edges)

  • Method Details

    • addEdge

      public void addEdge(int[] edge)

    • shortestPath

      public int shortestPath(int node1, int node2)