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

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading…

1360 words
Last Post: Teaching Kids Programming – Depth First/Limit Search and Iterative Deepening Search Algorithm on Unweighted Graph
Next Post: Teaching Kids Programming – Recursive Algorithm to Prune a Binary Tree