Minimal range electric car needs to have to pass through every city

Update:

While MST (minimum spanning tree) works for this problem, it probably¹ doesn't have the optimal time complexity. The problem should be considered as MSBT (minimum bottleneck spanning tree) instead, for which algorithms with linear time complexity in term of number of edges exist, such as Camerini's_algorithm.

You are looking for the maximum edge of the MST. There are many well-known algorithms for finding MST, of which Kruskal's and Prim's (which btilly uses in his answer) are the easiest to implement.

It is easy to see, why the maximum edge of MST is enough to drive through every city: you can traverse all cities, fully charging in each city and driving only roads that belong to the tree.

The range of at least the maximum edge of MST is required, because otherwise you will not be able to visit both cities that this edge is connected. This can be seen from the way Kruskal's algorithm is constructed. If only edges less that the maximum edge of MST are taken, then Kruskal's algorithm will fail to join all vertices into a single connected component.

Let's assume that there is a minimal spanning tree with an edge that is larger than the maximal edge of some other (minimal or not) spanning tree. Then we'll try to replace it with a smaller one. To do this, firstly delete this edge. Now we are left with two sets of vertices. The second tree must connect these sets with an edge. Lets take this edge and add it to the first tree. As this edge is smaller than the deleted one, then we've got a tree that has sum of edges less than minimal spanning tree, so the tree can't be minimal spanning tree in the first place and there is contradiction. In conclusion:

• the larger spanning tree can't have smaller maximal edge
• all maximal edges of every minimal spanning the tree are the same

The first statement means that the MST is the tree to look for solution, and the second statement means that it doesn't matter, which algorithm to use to find the MST

The key concept that you need is a priority queue which is usually implemented with a heap. This is a data structure that allows you to put things in with some sort of weight, and then pull out the lowest weight one.

Let's also use a set of things.

The idea now is this. We start somewhere. We have a priority queue of ways of getting to another city. We always look at the shortest-range drive that gets to that city. If it gets to a new to us city, we add it to the cities we can get to, and update our range if this was a longer drive than any other that we've seen.

Once we've visited all cities, we're done.

Now here is pseudo-code.

choose a start_city
initialize set visited_cities
initialize priority queue named queue to (0, start_city)
initialize min_range = 0

while len(visited_cities) < number of cities:
    (distance, city) = queue.pop()
    if city not in visited_cities:
        min_range = max(min_range, distance)
        visited_cities.add(city)
        for other_city in all cities:
            if other_city not in visited_cities:
                queue.add(distance from city to other_city, other_city)

min_range is the answer