⏲️

Network Delay Time Problem Using Dijkstra's Algorithm

Jul 10, 2024

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.

Full transcript