Problem Solving/LeetCode
2023.11.13 Today's Challenge
fabichoi
2023. 11. 13. 23:45
Design Graph With Shortest Path Calculator - LeetCode
Can you solve this real interview question? 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 e
leetcode.com
다익스트라 알고리즘으로 푸는 문제
class Graph:
def __init__(self, n: int, edges: List[List[int]]):
self.adj_list = [[] for _ in range(n)]
for from_node, to_node, cost in edges:
self.adj_list[from_node].append((to_node, cost))
def addEdge(self, edge: List[int]) -> None:
from_node, to_node, cost = edge
self.adj_list[from_node].append((to_node, cost))
def shortestPath(self, node1: int, node2: int) -> int:
n = len(self.adj_list)
pq = [(0, node1)]
cost_for_node = [inf] * (n)
cost_for_node[node1] = 0
while pq:
curr_cost, curr_node = heappop(pq)
if curr_cost > cost_for_node[curr_node]:
continue
if curr_node == node2:
return curr_cost
for neighbor, cost in self.adj_list[curr_node]:
new_cost = curr_cost + cost
if new_cost < cost_for_node[neighbor]:
cost_for_node[neighbor] = new_cost
heappush(pq, (new_cost, neighbor))
return -1
반응형