Teaching Kids Programming – Floyd Warshall Multi-source/All Pairs Shortest Path Algorithm (Sum of Costs in a Directed Unweighted Graph) | ninjasquad
Teaching Kids Programming: Videos on Data Structures and Algorithms
Shipping and Receiving: Sum of Costs (Shortest Path) of Pairs of Vertex in a Directed Unweighted Graph
You are given a two-dimensional list of integers ports where ports[i] represents the list of ports that port i is connected to. You are also given another two-dimensional list of integers shipments where each list of the form [port_i, port_j] which means there is a shipment request from port_i to port_j.
Given that the cost to ship port_i to port_j is the length of the shortest path from the two ports, return the total cost necessary to send all the shipments. If there’s not a path between two ports, the cost is 0.
Constraints
p ≤ 100 where p is the length of ports
s ≤ 10,000 where s is the length of shipments
Example 1
Input
1 2 3 4 5 6 7 8 9 10 ports = [ [2, 3], [2], [1, 0], [4], [] ] shipments = [ [2, 4] ]ports = [ [2, 3], [2], [1, 0], [4], [] ] shipments = [ [2, 4] ]Output
3
Floyd Warshal Multi-source/All Pairs Shortest Path Algorithm (Sum of Costs in a Directed Unweighted Graph)
First of all, we need to be able to compute the shortest path between any pairs of vertex. We can use the Floyd Warshal which is a multi source (all pairs) shortest path algorithm that runs at O(N^3) time complexity where N is the number of vertex. And the space complexity is O(N^2).
Floyd Warshal can be used on a Directed/Undirected Weighted/Unweighted Graph, as long as the Graph does not contain negative weight cycle otherwise we can traverse the cycle one more time to find a shorter path. Of course, if we don’t allow re-visiting same vertex in the path, there is a shortest path.
The Floyd Warshal is based on the Following Dynamic Programming concept: if we find a vertex k and the sum of d[i][k]+d[k][j] is smaller than current cost d[i][j], then we update it.
First, we need to convert the Graph from Adjacent List to Adjacent Matrix. Then we can compute the shortest path (all pairs) using O(N^3) loops:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution: def solve(self, G, paths): n = len(G) d = [[0 if i == j else inf for i in range(n)] for j in range(n)] for i, v in enumerate(G): for j in v: d[i][j] = 1 for k in range(n): for i in range(n): for j in range(n): d[i][j] = min(d[i][j], d[i][k] + d[k][j]) return sum(d[i][j] if d[i][j] != inf else 0 for i, j in paths) |
class Solution: def solve(self, G, paths): n = len(G) d = [[0 if i == j else inf for i in range(n)] for j in range(n)] for i, v in enumerate(G): for j in v: d[i][j] = 1 for k in range(n): for i in range(n): for j in range(n): d[i][j] = min(d[i][j], d[i][k] + d[k][j]) return sum(d[i][j] if d[i][j] != inf else 0 for i, j in paths)
We can use the Cartesian Product (aka the itertools.product function) to bruteforce the tuplet:
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution: def solve(self, G, paths): n = len(G) d = [[0 if i == j else inf for i in range(n)] for j in range(n)] for i, v in enumerate(G): for j in v: d[i][j] = 1 for k, i, j in product(range(n), repeat=3): d[i][j] = min(d[i][j], d[i][k] + d[k][j]) return sum(d[i][j] if d[i][j] != inf else 0 for i, j in paths) |
class Solution: def solve(self, G, paths): n = len(G) d = [[0 if i == j else inf for i in range(n)] for j in range(n)] for i, v in enumerate(G): for j in v: d[i][j] = 1 for k, i, j in product(range(n), repeat=3): d[i][j] = min(d[i][j], d[i][k] + d[k][j]) return sum(d[i][j] if d[i][j] != inf else 0 for i, j in paths)
Shortest Path Algorithms
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading…
1208 words
Last Post: Teaching Kids Programming – Introduction to Cartesian Product (Math)
Next Post: How to Delete/Remove Kubernetes – Azure Arc using CLI without kubeconfig or connected to cluster?
Source: Internet