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.

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?