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

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:

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:

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

• Teaching Kids Programming – Distance Between Bus Stops (Floyd Warshal Shortest Path in Simple Undirected Weighted Regular Graph)
• Teaching Kids Programming – Depth First/Limit Search and Iterative Deepening Search Algorithm on Unweighted Graph
• Teaching Kids Programming – A Light Talk on Breadth First Search, Uniform Cost Search and Dijkstra Shortest Path Graph Algorithms
• Teaching Kids Programming – Introduction to Dijkstra Single Source Shortest Path Graph Algorithm
• Teaching Kids Programming – Single Source Shortest Path Algorithm in a Directed Unweighted Graph using Breadth First Search
• Teaching Kids Programming – Floyd Warshal Multi-source/All Pairs Shortest Path Algorithm (Sum of Costs in a Directed Unweighted Graph)
• Teaching Kids Programming – Uniform Cost Search Algorithm to Solve Single-Source Shortest Path in a Graph
• Teaching Kids Programming – Shortest Path Algorithms by Iterative Deepening Search (IDS), Depth First Search (DFS) or Breadth First Search (BFS) on Undirected Graphs
• Teaching Kids Programming – Finding the Network Delay Time via Floyd-Warshall Shortest Path Algorithm
• Teaching Kids Programming – Distance Between Bus Stops (Shortest Distance in Simple Undirected Weighted Regular Graph)

–EOF (The Ultimate Computing & Technology Blog) —