# Teaching Kids Programming – Floyd Warshall Multi-source/All Pairs Shortest Path Algorithm (Sum of Costs in a Directed Unweighted Graph)

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.

$tex_320922393d3ba13e28b53040a5914c8e Teaching Kids Programming - Floyd Warshall Multi-source/All Pairs Shortest Path Algorithm (Sum of Costs in a Directed Unweighted Graph) algorithms Floyd Warshal Graph Algorithm python teaching kids programming youtube video$

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)      ```

GD Star Rating