LeetCode, 𝐃𝐚𝐲-5/365-DSA-Coding 𝐉𝐨𝐮𝐫𝐧𝐞𝐲…

Today I Learned: Solving the “Network Delay Time” Problem in Python

The Problem:

Imagine a network with n nodes labeled from 1 to n. Signals are sent between nodes via direct connections, each having a transmission time. Given the array times (representing signal travel times between nodes), the number of nodes n, and a starting node k, your task is to calculate the time it will take for all nodes to receive the signal. If some nodes are unreachable, return -1.

This problem is commonly encountered in graph theory and algorithms, particularly when working with weighted graphs.

Logic I Used:

To solve this, I used Dijkstra’s algorithm, a popular method for finding the shortest paths in a weighted graph with non-negative edge weights. Here’s the logic:

1. Represent the network as a graph using an adjacency list.
2. Use a priority queue (min-heap) to explore nodes in order of increasing distance.
3. Update the shortest known distance for each node whenever a better path is found.
4. After processing all nodes, check the maximum distance among reachable nodes. If some nodes are unreachable, return -1.

Steps to Solve:

1️⃣ Represent the Network as a Graph

Use an adjacency list to map each node to a list of its neighbors and their respective costs:

adjList = [[] for _ in range(n + 1)]
for source, dest, cost in times:
    adjList[source].append((dest, cost))

2️⃣ Initialize Costs and Priority Queue

Set initial distances to infinity (float('inf')) except for the starting node (k), which is 0. Use a priority queue to manage nodes based on their current costs:

pq = [(0, k)]  # (cost, node)
costs = [float("inf")] * (n + 1)
costs[k] = 0

3️⃣ Process Nodes Using Dijkstra’s Algorithm

For each node:

• Pop the smallest cost node from the priority queue.
• Update its neighbors’ costs if a shorter path is found.
• Push updated costs into the queue.

4️⃣ Calculate the Result

After processing all nodes, find the maximum cost among reachable nodes:

max_cost = max(costs[1:])  # Skip costs[0], as nodes are 1-indexed
return max_cost if max_cost != float("inf") else -1

Other Possible Logics:

1. Bellman-Ford Algorithm:

• Use this if the graph has negative edge weights. It’s slower (O(n * e)) but reliable for such scenarios.

1. Floyd-Warshall Algorithm:

• A dynamic programming approach for all-pairs shortest paths. Suitable for dense graphs but less efficient for this problem (O(n^3)).

1. Breadth-First Search (BFS):

• If all edges have the same weight, BFS is simpler and faster than Dijkstra’s algorithm.

Algorithms in Depth:

Dijkstra’s Algorithm

• Time Complexity: O((n + e) * log(n)), where n is the number of nodes and e is the number of edges.
• Space Complexity: O(n + e) for the adjacency list and other data structures.

Bellman-Ford Algorithm

• Time Complexity: O(n * e)
• Best for graphs with negative weights.

Learnings:

1. Efficient graph representation matters — adjacency lists save space.
2. Priority queues are crucial for optimal performance in Dijkstra’s algorithm.
3. Understanding edge cases, like unreachable nodes, is vital for robust solutions.

Usage:

• Real-Life Applications:
• Optimizing data flow in networks (e.g., routing in computer networks).
• Planning shortest routes in GPS systems.
• Tech Interviews: This problem frequently appears in coding interviews to test your understanding of graph traversal and optimization algorithms.

Examples:

Input:

times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]
n = 4
k = 2

Output:

2

Explanation:

• Node 2 sends signals to nodes 1, 3, and 4.
• Signal reaches all nodes in 2 units of time.

Thanks for Reading!

If you’d like to discuss more or share alternative solutions, drop your suggestions below. Special thanks to icodeguru for guiding and supporting me on this coding journey. Let’s smile, code, live, love, and share together!

Stay curious and keep learning!