'What is the time complexity of Dijkstra's Algorithm? Am I implementing my code right?
I was trying to implement Dijkstra's SPA for the LeetCode Question #743, but I wasn't sure if my algorithm was written in the most efficient manner. Would I be able to get some feedbacks on how I can be improving my code? Also, I would like to get some explanations on my code's time complexity. Thanks!
The variables are:
- times: list of directed edges in [u, v, w] format. u is the source node, v is the target node, and w is the weight of the edge.
- n: number of nodes
- k: initial node
Here is my code:
def listToDict(self, times):
times_dict = defaultdict(list)
for edge in times:
u,v,w = edge
times_dict[u].append((w,v))
return times_dict
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
distances = [float("inf")] * (n)
# O(E)
graph_dict = self.listToDict(times)
nodes_to_visit = [(0,k)]
while nodes_to_visit:
w, u = heapq.heappop(nodes_to_visit)
if distances[u-1] > w:
distances[u-1] = w
for neighbor in graph_dict[u]:
w2, v = neighbor
if distances[v-1] == float("inf"):
heapq.heappush(nodes_to_visit, (w+w2, v))
if float("inf") in distances:
return -1
else:
return max(distances)
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|