# Algorithm for finding lowest cost edge in each path in a graph

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.

Any help or hints would be appreciated.

• I think your title is confusing - you actually need to find a path from $s$ to $v$, which minimizes maximum cost edge – HEKTO Dec 29 '16 at 21:58
• And look here: cs.stackexchange.com/questions/4942/… – HEKTO Dec 29 '16 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)\}$.
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$.