Teaching Kids Programming – Distance Between Bus Stops (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 (Shortest Distance in Simple Undirected Weighted Regular Graph)

This is a simple regular Graph where each vertex has a same number of neighbour vertices. This is also a undirected (edges/directions go both way) and weighted graph which has only one cycle. And there are only two routes between any two vertices, and thus we can compute them separately and return the minimal.

We can compute the direct distance (where start is smaller than stop) and let’s denote it x, and the other route has total – x where total is the sum of all the edges.

1
2
3
4
5
6
7

class Solution:
    def distanceBetweenBusStops(self, dist: List[int], start: int, stop: int) -> int:
        if start > stop:
            start, stop = stop, start
        total = sum(dist)
        x = sum(dist[start: stop])
        return min(total - x, x)

class Solution:
    def distanceBetweenBusStops(self, dist: List[int], start: int, stop: int) -> int:
        if start > stop:
            start, stop = stop, start
        total = sum(dist)
        x = sum(dist[start: stop])
        return min(total - x, x)

Another algorithm or approach is to sum the distance before the start and after the stop:

1
2
3
4
5

class Solution:
    def distanceBetweenBusStops(self, dist: List[int], start: int, stop: int) -> int:
        if start > stop:
            start, stop = stop, start
        return min(sum(dist[:start]) + sum(dist[stop:]), sum(dist[start: stop]))

class Solution:
    def distanceBetweenBusStops(self, dist: List[int], start: int, stop: int) -> int:
        if start > stop:
            start, stop = stop, start
        return min(sum(dist[:start]) + sum(dist[stop:]), sum(dist[start: stop]))

Since this is a Graph, we can also apply the shortest graph algorithms such as Floyd Warshal. However, the time complexity O(N) is optimal on this simple graph problem.

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