Teaching Kids Programming – Distance Between Bus Stops (Floyd Warshall Shortest Path in Simple Undirected Weighted Regular Graph)

Teaching Kids Programming: Videos on Data Structures and Algorithms

A bus has n stops numbered from 0 to n – 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n. The bus goes along both directions i.e. clockwise and counterclockwise. Return the shortest distance between the given start and destination stops.

Example 1:
Input: distance = [1,2,3,4], start = 0, destination = 1
Output: 1
Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.

Example 2:
Input: distance = [1,2,3,4], start = 0, destination = 2
Output: 3
Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.

Example 3:
Input: distance = [1,2,3,4], start = 0, destination = 3
Output: 4
Explanation: Distance between 0 and 3 is 6 or 4, minimum is 4.

distance-between-bus-stops

Constraints:
1 <= n <= 10^4
distance.length == n
0 <= start, destination < n
0 <= distance[i] <= 10^4

Hint:
Find the distance between the two stops if the bus moved in clockwise or counterclockwise directions.

Distance Between Bus Stops (Floyd Warshall Shortest Distance in Simple Undirected Weighted Regular Graph)

This is a special regular graph (weighted and directed) where each node has a same number of vertices. We can apply the shortest graph algorithms to solve this particular graph problem. Floyd Warshall is a multi-source weighted graph shortest path algorithms that is based on the Dynamic Programming Concept.

The idea is to bruteforce all pairs of vertices (i, j) and then also bruteforce each vertice . And then replace with a shorter path if we find the distance from i to j can be optimised to the sum of distance i to k and k to j.

Then first, we need to convert the input (distance array) to the Graph using Adjacency Matrix where d[i][j] is the weight between vertex i to vertex j. Since this is undirected, d[i][j] is equal to d[j][i].

Then we apply the Floyd Warshal Shortest Distance Algorithm on the Graph.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def distanceBetweenBusStops(self, dist: List[int], start: int, stop: int) -> int:
        n = len(dist)
        d = [[inf] * n for _ in range(n)]
        for i in range(n - 1):
            d[i + 1][i] = d[i][i + 1] = dist[i]
            
        d[0][n - 1] = d[n - 1][0] = dist[-1]
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][k] + d[k][j], d[i][j])
        
        return d[start][stop]

class Solution:
    def distanceBetweenBusStops(self, dist: List[int], start: int, stop: int) -> int:
        n = len(dist)
        d = [[inf] * n for _ in range(n)]
        for i in range(n - 1):
            d[i + 1][i] = d[i][i + 1] = dist[i]
            
        d[0][n - 1] = d[n - 1][0] = dist[-1]
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][k] + d[k][j], d[i][j])
        
        return d[start][stop]

We can use the itertools.product (the Cartesian Product) to beautify the for loops.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def distanceBetweenBusStops(self, dist: List[int], start: int, stop: int) -> int:
        n = len(dist)
        d = [[inf] * n for _ in range(n)]
        for i in range(n - 1):
            d[i + 1][i] = d[i][i + 1] = dist[i]
            
        d[0][n - 1] = d[n - 1][0] = dist[-1]
        
        for k, i, j in itertools.product(range(n), repeat=3):
            d[i][j] = min(d[i][k] + d[k][j], d[i][j])
        
        return d[start][stop]

class Solution:
    def distanceBetweenBusStops(self, dist: List[int], start: int, stop: int) -> int:
        n = len(dist)
        d = [[inf] * n for _ in range(n)]
        for i in range(n - 1):
            d[i + 1][i] = d[i][i + 1] = dist[i]
            
        d[0][n - 1] = d[n - 1][0] = dist[-1]
        
        for k, i, j in itertools.product(range(n), repeat=3):
            d[i][j] = min(d[i][k] + d[k][j], d[i][j])
        
        return d[start][stop]

The time complexity for Floyd Warshall Multi source shortest path/distance algorithm is , and the space complexity is .

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