aboutsummaryrefslogtreecommitdiff
path: root/design_graph_short_path.py
diff options
context:
space:
mode:
Diffstat (limited to 'design_graph_short_path.py')
-rw-r--r--design_graph_short_path.py51
1 files changed, 51 insertions, 0 deletions
diff --git a/design_graph_short_path.py b/design_graph_short_path.py
new file mode 100644
index 0000000..d41a51d
--- /dev/null
+++ b/design_graph_short_path.py
@@ -0,0 +1,51 @@
+# 2642. Design Graph With Shortest Path Calculator
+
+"""
+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] = [from[i], to[i], edge_cost[i]]' meaning that
+there is an edge from 'from[i]' to 'to[i]' with the cost 'edge_cost[i]'.
+"""
+
+
+class Graph(object):
+ def __init__(self, n, edges):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ """
+ self.N = n
+ self.INF = 10**19
+ adj_list = collections.defaultdict(list)
+ for u, v, wt in edges:
+ adj_list[u].append((v, wt))
+ self.adj_list = adj_list
+
+ def addEdge(self, edge):
+ """
+ :type edge: List[int]
+ :rtype: None
+ """
+ self.adj_list[edge[0]].append((edge[1], edge[2]))
+
+ def shortestPath(self, node1, node2):
+ """
+ :type node1: int
+ :type node2: int
+ :rtype: int
+ """
+ h = []
+ heapq.heappush(h, (0, node1))
+ dist = [self.INF] * self.N
+ dist[node1] = 0
+ while len(h):
+ d, u = heapq.heappop(h)
+ if u == node2:
+ return d
+ if dist[u] < d:
+ continue
+ for v, wt in self.adj_list[u]:
+ if dist[v] > dist[u] + wt:
+ dist[v] = dist[u] + wt
+ heapq.heappush(h, (dist[v], v))
+ return -1