Teaching Kids Programming – Finding the Network Delay Time via Floyd-Warshall Shortest Path Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target. We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:

DAG = Directed Acyclic Graph

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Example 2:
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Example 3:
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

Constraints:
1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

Hints:
We visit each node at some time, and if that time is better than the fastest time we’ve reached this node, we travel along outgoing edges in sorted order. Alternatively, we could use Dijkstra’s algorithm.

Compute the Max Network Delay Time via Floyd-Warshall Shortest Path Algorithm

Floyd-Warshall Algorithm can be used to compute the shortest distance beween any two pairs of vertices in a Graph in O(N^3) time and O(N^2) space.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        dist = [[math.inf for _ in range(N)] for _ in range(N)]
        for u, v, w in times:
            dist[u - 1][v - 1] = w
        for i in range(N):
            dist[i][i] = 0
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return max(dist[K-1]) if max(dist[K-1]) < math.inf else -1         

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        dist = [[math.inf for _ in range(N)] for _ in range(N)]
        for u, v, w in times:
            dist[u - 1][v - 1] = w
        for i in range(N):
            dist[i][i] = 0
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return max(dist[K-1]) if max(dist[K-1]) < math.inf else -1         

If a vertice is unreachable, the shortest distance i.e. dist[][] will be math.inf. On initialization, dis[a][a] value will be set to zero.

Shortest Path Algorithms

• Teaching Kids Programming – Distance Between Bus Stops (Floyd Warshal Shortest Path in Simple Undirected Weighted Regular Graph)
• Teaching Kids Programming – Depth First/Limit Search and Iterative Deepening Search Algorithm on Unweighted Graph
• Teaching Kids Programming – A Light Talk on Breadth First Search, Uniform Cost Search and Dijkstra Shortest Path Graph Algorithms
• Teaching Kids Programming – Introduction to Dijkstra Single Source Shortest Path Graph Algorithm
• Teaching Kids Programming – Single Source Shortest Path Algorithm in a Directed Unweighted Graph using Breadth First Search
• Teaching Kids Programming – Floyd Warshal Multi-source/All Pairs Shortest Path Algorithm (Sum of Costs in a Directed Unweighted Graph)
• Teaching Kids Programming – Uniform Cost Search Algorithm to Solve Single-Source Shortest Path in a Graph
• Teaching Kids Programming – Shortest Path Algorithms by Iterative Deepening Search (IDS), Depth First Search (DFS) or Breadth First Search (BFS) on Undirected Graphs
• Teaching Kids Programming – Finding the Network Delay Time via Floyd-Warshall Shortest Path Algorithm
• Teaching Kids Programming – Distance Between Bus Stops (Shortest Distance in Simple Undirected Weighted Regular Graph)

–EOF (The Ultimate Computing & Technology Blog) —