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