Design Graph With Shortest Path Calculator — LeetCode 2642 Python Solution
HardGraphDesignShortest PathHeap (Priority Queue)
- Problem
- #2642
- Pattern
- Heap / Priority Queue
- Reading time
- 6 min
- Source
- leetcode.com
The problem
There is a directed weighted graph that consists of n nodes numbered from 0 to n - 1. The edges of the graph are initially represented by the given array edges where edges[i] = [fromi, toi, edgeCosti] meaning that there is an edge from fromi to toi with the cost edgeCosti.
Example
- Input
- ["Graph", "shortestPath", "shortestPath", "addEdge", "shortestPath"]
- Output
- [null, 6, -1, null, 6]
- Explanation
- Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]);
Python solution
Python
class Graph:
def __init__(self, n: int, edges: List[List[int]]):
self.n = n
self.g = [[inf] * n for _ in range(n)]
for f, t, c in edges:
self.g[f][t] = c
def addEdge(self, edge: List[int]) -> None:
f, t, c = edge
self.g[f][t] = c
def shortestPath(self, node1: int, node2: int) -> int:
dist = [inf] * self.n
dist[node1] = 0
vis = [False] * self.n
for _ in range(self.n):
t = -1
for j in range(self.n):
if not vis[j] and (t == -1 or dist[t] > dist[j]):
t = j
vis[t] = True
for j in range(self.n):
dist[j] = min(dist[j], dist[t] + self.g[t][j])
return -1 if dist[node2] == inf else dist[node2]
# Your Graph object will be instantiated and called as such:
# obj = Graph(n, edges)
# obj.addEdge(edge)
# param_2 = obj.shortestPath(node1,node2)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n^2 \times q) |
| Space | O(n^2) auxiliary |
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2642. Design Graph With Shortest Path Calculator is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
LeetCode 743Network Delay TimeMediumLeetCode 882Reachable Nodes In Subdivided GraphHardLeetCode 1368Minimum Cost to Make at Least One Valid Path in a GridHardLeetCode 1514Path with Maximum ProbabilityMediumLeetCode 2290Minimum Obstacle Removal to Reach CornerHardLeetCode 2577Minimum Time to Visit a Cell In a GridHard
Frequently asked questions
- How hard is LeetCode 2642. Design Graph With Shortest Path Calculator?
- LeetCode 2642. Design Graph With Shortest Path Calculator is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2642. Design Graph With Shortest Path Calculator?
- The Python solution on this page runs in O(n^2 \times q).
- What is the space complexity of LeetCode 2642. Design Graph With Shortest Path Calculator?
- The Python solution on this page uses O(n^2) auxiliary space.
- What topics does LeetCode 2642. Design Graph With Shortest Path Calculator cover?
- LeetCode 2642. Design Graph With Shortest Path Calculator is tagged Graph, Design, Shortest Path and Heap (Priority Queue) on LeetCode.