#2642

Design Graph With Shortest Path Calculator

expert · 1085 · lc hard +32 · 64.9% accepted · 875 likes · top 69%

⚑ Floyd-Warshall (All-Pairs Shortest Path)

Description

Design a Graph class for a directed weighted graph with n nodes numbered 0 to n - 1. Implement: a constructor accepting n and an initial edge list, an addEdge method to insert a new directed weighted edge, and a shortestPath method returning the minimum-cost path between two nodes (or -1 if none exists).

Example 1:

Input

["Graph", "shortestPath", "shortestPath", "addEdge", "shortestPath"]

[[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]]

Output

[null, 6, -1, null, 6]

Example 2:

Explanation

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.

g.shortestPath(0, 3); // return -1. There is no path from 0 to 3.

g.addEdge([1, 3, 4]); // We add an edge from node 1 to node 3, and we get the second diagram above.

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.

Code

class Graph:

    def __init__(self, n: int, edges: List[List[int]]):
        

    def addEdge(self, edge: List[int]) -> None:
        

    def shortestPath(self, node1: int, node2: int) -> int:
        


# Your Graph object will be instantiated and called as such:
# obj = Graph(n, edges)
# obj.addEdge(edge)
# param_2 = obj.shortestPath(node1,node2)

class Graph:

    def __init__(self, n: int, edges: List[List[int]]):
        

    def addEdge(self, edge: List[int]) -> None:
        

    def shortestPath(self, node1: int, node2: int) -> int:
        


# Your Graph object will be instantiated and called as such:
# obj = Graph(n, edges)
# obj.addEdge(edge)
# param_2 = obj.shortestPath(node1,node2)