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

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

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.

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. $tex_8f6925a1ffcebdf4e20f131d0d91d7a8 Teaching Kids Programming - Distance Between Bus Stops (Floyd Warshall Shortest Path in Simple Undirected Weighted Regular Graph) algorithms Floyd Warshal geometry graph Graph Algorithm graphs math python teaching kids programming youtube video$

The idea is to bruteforce all pairs of vertices (i, j) and then also bruteforce each vertice $tex_6aa5e3d99a5ffc3d0db25668d5a36957 Teaching Kids Programming - Distance Between Bus Stops (Floyd Warshall Shortest Path in Simple Undirected Weighted Regular Graph) algorithms Floyd Warshal geometry graph Graph Algorithm graphs math python teaching kids programming youtube video$. 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[n - 1] = d[n - 1] = 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[n - 1] = d[n - 1] = 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 $tex_7a76d6674dd1fcfdd41f44c3fcd0f07a Teaching Kids Programming - Distance Between Bus Stops (Floyd Warshall Shortest Path in Simple Undirected Weighted Regular Graph) algorithms Floyd Warshal geometry graph Graph Algorithm graphs math python teaching kids programming youtube video$ 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[n - 1] = d[n - 1] = 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[n - 1] = d[n - 1] = 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 $tex_7a76d6674dd1fcfdd41f44c3fcd0f07a Teaching Kids Programming - Distance Between Bus Stops (Floyd Warshall Shortest Path in Simple Undirected Weighted Regular Graph) algorithms Floyd Warshal geometry graph Graph Algorithm graphs math python teaching kids programming youtube video$, and the space complexity is $tex_84dc4634ea26f37367902b093c57dc5c Teaching Kids Programming - Distance Between Bus Stops (Floyd Warshall Shortest Path in Simple Undirected Weighted Regular Graph) algorithms Floyd Warshal geometry graph Graph Algorithm graphs math python teaching kids programming youtube video$.

GD Star Rating