# Given a vertex, find a path between it and each other vertex that minimizes the maximum weight in the path

I'm revising for an upcoming exam and was wondering if someone could help me with a practice problem:

We model a set of cities and highways as an undirected weighted graph $$G = (V,E,l)$$, where the vertices $$V$$ represent cities, edges $$E$$ represent highways connecting cities, and for every undirected edge $$e = \{v, w\}\in E$$ the number $$\ell[e]$$ denotes the number of litres of fuel that your motorcycle needs in order to ride the distance between cities $$v$$ and $$w$$. There are fuel stations in every city but none on the highways between the cities. Therefore, if the capacity of your motorcycle's fuel tank is $$L$$ litres, then you can only follow a path (a sequence of adjacent highways), if for every highway $$e$$ on this path, we have $$L\geq \ell[e]$$, because you can only refuel in the cities.

Design an algorithm with a running of time of $$O(m\log n)$$ that, given an undirected weighted graph $$G=(V,E,\ell)$$ modelling a setting of cities and highways, and a city $$s \in V$$ as inputs, computes for every other city $$v \in V$$, the smallest fuel tank capacity $$M[v]$$ that your motorcycle needs in order to be able to reach city $$v$$ from city $$s$$.

I'm not sure how to solve this problem, but I do have a few ideas. I thought of possibly running Kruskal's algorithm since that would give me the MST of the graph. I'm not sure how I would then efficiently get the answer I need to produce.

Alternatively, I was thinking of using dynamic programming in some way since that's one of the things that we use a lot in the course, but I'm not really sure how to go about it.

• I think your title is confusing - you actually need to find a path from $s$ to $v$, which minimizes maximum cost edge Commented Dec 29, 2016 at 21:58
• And look here: cs.stackexchange.com/questions/4942/… Commented Dec 29, 2016 at 22:01

Let $T = \{s\}$, and let $Q$ be a new empty priority queue. Insert each edge incident on $s$ in $Q$. While there are still nodes with $d$ from $s$ yet to be computed, extract and remove the minimum from $Q$.

If such edge connects a node $u$ in $T$ with a node $v$ not in $T$, add each edge incident on $v$ that still isn't in $Q$ to $Q$, then set $M[v]$ to $\max\{M[u], w(u, v)\}$.

Otherwise, disregard the extracted edge and extract more edges until you find a suitable one.

The overall complexity is $O(|E| \log |E|) = O(|E| \log |V|^2) = O(|E| \log |V|)$.

To informally prove correctness, we can observe that whenever we set $M[v]$ to a certain value $x$, we can certainly reach $v$ from $s$ with a path in which each edge weighs at most $x$. On the other hand, no better path exists, because we already gave each edge lighter than $x$ a chance to connect to $s$.

• "While there are still nodes with $d$ from $s$ yet to be computed, ..." What is $d$? Commented Dec 14, 2019 at 17:12

It's modification of Dijkstra algorithm. In Dijkstra you take minimum of distance from beginning to visited plus distance to not visited adjacent, here you take minimum of max { visited, not visited adjacent }.