Lecture Notes: Network Delay Time Problem

Introduction

• Topic: Solving network delay time using Dijkstra's Algorithm.
• Graph Problem: Given a network of n nodes labeled from 1 to n and a list of times representing directed edges with weights.
• Objective: Starting from a given node k, determine the time required for a signal to reach all nodes.
• Output: Return the time to visit all nodes or -1 if not all nodes can be reached.

Key Concepts

1. Graph Representation: Directed edges with weights.
   • times list of triples (u, v, w) where u is the source node, v is the target node, and w is the weight.
2. Initial Node: k is the starting point node.
3. Breadth First Search (BFS): Dijkstra's Algorithm is a form of BFS but uses a minimum heap (priority queue).
4. Minimum Heap: Data structure required for Dijkstra's Algorithm to efficiently get the minimum value.

Example Walkthrough

• Example graph with directed edges and weights.
• Start at node 2 (k=2).
• Compute the time to reach each node:
  • Node 2, 1: Time = 1
  • Node 3, 4: Time = 2 (1+1)
• Output: Maximum time value among the reachable nodes.

Dijkstra's Algorithm Steps

1. Initialize:
   • Min Heap with starting node with path length 0.
   • Set to keep track of visited nodes.
   • Variable t for result.
2. Algorithm:
   • While the min heap is not empty:
     • Pop the value from the min heap (shortest path first).
     • Skip if the node is already visited.
     • Otherwise, mark the node as visited and update t.
     • Perform BFS by iterating over the neighbors of the current node:
       • For unvisited neighbors, calculate the new path length and add to the min heap.
3. Termination:
   • If all nodes are visited, return t.
   • If all nodes are not visited, return -1.

Time Complexity Analysis

• E: Number of edges.
• V: Number of vertices (nodes).
• Heap Operations: Worst-case O(log V^2)
• Overall Complexity: O(E log V)

Implementation in Code

Steps

1. Create adjacency list for the graph from the given edges.
2. Initialize min heap starting from node k with path length 0.
3. Create set visit to keep track of visited nodes.
4. Initialize result t to 0.
5. Perform Dijkstra's Algorithm using min heap for BFS.
6. Return result t if all nodes are visited; otherwise return -1.

Example Python Code Snippet

import heapq

def networkDelayTime(times, n, k):
    edges = {i: [] for i in range(1, n + 1)}
    for u, v, w in times:
        edges[u].append((v, w))

    min_heap = [(0, k)]
    visit = set()
    t = 0
    while min_heap:
        w1, n1 = heapq.heappop(min_heap)
        if n1 in visit:
            continue
        visit.add(n1)
        t = max(t, w1)

        for n2, w2 in edges[n1]:
            if n2 not in visit:
                heapq.heappush(min_heap, (w1 + w2, n2))

    return t if len(visit) == n else -1

Conclusion

• Dijkstra's Algorithm is essential for solving shortest path problems in graphs.
• Network delay problem demonstrates the application of this algorithm.
• Complexity analysis shows the practicality and limitations of the approach.