Leetcode 743:Network Delay Time — Dijkstra’s algorithm(Python)

Photo by James Harrison on Unsplash

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        d=collections.defaultdict(list)
        for u,v,w in times:
            d[u].append([v,w])
        visit=set()
        minHeap=[[0,k]]
        t=0
        while minHeap:
            w1,n1=heapq.heappop(minHeap)
            if n1 in visit:
                continue
            visit.add(n1)
            t=max(t,w1)
            for n2,w2 in d[n1]:
                heapq.heappush(minHeap,[w1+w2,n2])
        return t if len(visit)==n else -1        

Here’s a step-by-step explanation of the code:

1. Data Structure Setup:

• d = collections.defaultdict(list): Creates a dictionary d to store the network connections. Each key will represent a node (source node), and its value will be a list of lists, where each inner list contains a destination node and the weight (time) of the connection between them.
• visit = set(): Creates an empty set visit to keep track of visited nodes, ensuring we don't visit them multiple times.
• minHeap = [[0, k]]: Creates a min-heap minHeap to prioritize nodes with the minimum total time to reach them. It's initialized with [0, k], indicating that the starting time is 0 and the starting node is k.

2. Building the Graph:

• for u, v, w in times:: Iterates through the times list, which contains information about connections (source node u, destination node v, and weight w).
• d[u].append([v, w]): Adds the connection details ([v, w]) to the list of connections for the source node u in the d dictionary.

3. Dijkstra’s Algorithm (Finding Shortest Paths):

• while minHeap:: Continues until the min-heap is empty (all reachable nodes have been visited).
• w1, n1 = heapq.heappop(minHeap): Pops the node with the minimum total time from the min-heap, storing its time as w1 and its node as n1.
• if n1 in visit:: Checks if the node has already been visited. If so, skips to the next iteration.
• visit.add(n1): Adds the node n1 to the visit set, marking it as visited.
• t = max(t, w1): Updates the overall maximum time t with the current node's total time w1.
• for n2, w2 in d[n1]: Iterates through the neighbors (n2) and their connection weights (w2) from the current node n1.
• heapq.heappush(minHeap, [w1 + w2, n2]): Pushes the neighbor nodes onto the min-heap with their updated total time (w1 + w2) to explore them later.

4. Determining Result:

• return t if len(visit) == n else -1: If all nodes have been visited (len(visit) == n), returns the maximum time t as the answer. Otherwise, returns -1, indicating that not all nodes are reachable from the starting node k.

Time Complexity:

• Building the graph: O(E), where E is the number of connections in times.
• Dijkstra’s algorithm: O(E log V), where V is the number of nodes in the graph. This is due to:
• Pushing nodes onto the min-heap: O(log V) for each node.
• Heap operations (pop, push): O(log V) each.
• Visiting each node (and its neighbors) at most once.
• Overall time complexity: O(E log V), dominated by Dijkstra’s algorithm.

Space Complexity:

• Graph representation (d): O(E) to store connections.
• Visited set (visit): O(V) to track visited nodes.
• Min-heap (minHeap): At most O(V) nodes in the heap at any time.
• Other variables: O(1) space for variables like t, w1, n1, etc.
• Overall space complexity: O(E + V) due to the graph and visited set.