algoadvance

  1. What is the input to this problem?
    • A list of times, where each element times[i] is of the form [u, v, w], representing a directed edge from node u to node v with travel time w.
    • An integer N, representing the total number of nodes.
    • An integer K, representing the starting node.
  2. What is the expected output?
    • The minimum time it will take for all nodes to receive the signal sent from node K. If it is impossible for all nodes to receive the signal, return -1.
  3. Can nodes have directed edges to themselves?
    • This usually doesn’t affect the outcome, but it’s useful to know.
  4. Are there any constraints on travel times?
    • Travel times are non-negative integers.

Strategy

This problem can be solved using graph algorithms like Dijkstra’s algorithm, which is well-suited for finding the shortest path in a graph with non-negative weights.

  1. Data Representation: Use an adjacency list to store the graph representation.

  2. Algorithm Choice: Utilize Dijkstra’s algorithm to find the shortest time to each node starting from node K.

  3. Priority Queue: Use a priority queue (min-heap) to always extend the shortest known path.

Steps:

  1. Create an adjacency list to represent the graph.
  2. Use a min-heap (priority queue) initialized with the starting node K.
  3. Use a dictionary to store the shortest known travel time to each node.
  4. Iterate until the priority queue is empty:
    • Extract the node with the smallest travel time.
    • Update travel times to its neighbors.
    • Add/Update neighbors in the priority queue.
  5. After the loop, check if all nodes are reachable.
  6. Return the maximum travel time in the dictionary if all nodes are reachable; otherwise, return -1.

Time Complexity

where V is the number of nodes and E is the number of edges.

Implementation

Let’s go ahead and implement this:

import heapq
from collections import defaultdict

def networkDelayTime(times, N, K):
    # Create a graph in the form of an adjacency list
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((w, v))
    
    # Priority queue to hold (travel_time, node)
    min_heap = [(0, K)]
    
    # Dictionary to store the shortest travel time to each node
    shortest_time = {}
    
    while min_heap:
        travel_time, node = heapq.heappop(min_heap)
        
        if node in shortest_time:
            continue
        
        shortest_time[node] = travel_time
        
        for time, neighbor in graph[node]:
            if neighbor not in shortest_time:
                heapq.heappush(min_heap, (travel_time + time, neighbor))
    
    # Check if we visited all nodes
    if len(shortest_time) == N:
        return max(shortest_time.values())
    else:
        return -1

# Example usage
times = [[2,1,1],[2,3,1],[3,4,1]]
N = 4
K = 2
print(networkDelayTime(times, N, K))  # Output: 2

Explanation

  1. Graph Construction (Adjacency List):
    • We populate the graph structure with the input edges.
  2. Priority Queue Initialization:
    • We initialize the priority queue with the starting node K and a travel time of 0.
  3. Processing Nodes:
    • While there are nodes in the priority queue, we process each node by extending paths to its neighbors if a shorter path is found.
  4. Checking Reachability:
    • After processing, we check if we have the shortest paths to all N nodes. If true, we return the maximum travel time; otherwise, -1.

This approach ensures that we efficiently find the shortest path to each node in the network using Dijkstra’s algorithm with a min-heap.

Try our interview co-pilot at AlgoAdvance.com