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


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)      

Shortest Path Algorithms

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
1171 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?

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

Leave a Reply