0
$\begingroup$

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.

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

2 Answers 2

0
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ "While there are still nodes with $d$ from $s$ yet to be computed, ..." What is $d$? $\endgroup$
    – xskxzr
    Dec 14, 2019 at 17:12
0
$\begingroup$

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 }.

$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .