0
$\begingroup$

Let $G(V,E)$, a directed graph with weighted edges ($w:E\to \mathbb{R}$) and a $r\in V$. It is known that for each $u$ there's a lightest path (by weights) which is also a shortest path (by edges), from $r$ to $u$. Describe an algorithm to find lightest paths from $r$ to each $u$.

So what I thought about is simply running a BFS algorithm from $r$ with a simple change; When we reach a vertex $v$, we sort all edges coming out of it and put vertices in queue by edges order (from smallest to largest).

This way we are getting a graph of shortest paths (As BFS should do) but we also prefer the lightest one from two shortest paths.

Let's assume my algorithm is correct, the problem is that it's not the most efficient one, since we have to sort all edges which summed up to $O(|E|\log |E|)$.

How can it be done in linear time ($O(|V|+|E|$)?

$\endgroup$

1 Answer 1

1
$\begingroup$

You can use a modified BFS to achieve linear running time. We consider the BFS search tree in levels.

  1. Start at the first level $V_{lev} = \{r\}$.
  2. Set $f(r) = 0$.
  3. $V_{lev}^{new} = \emptyset$
  4. For each $v \in V_{lev}$

    4.1 For each $w$ adjacent to $v$ update $f(w) = f(v) + w(v,w)$ if necessary.

    4.2 Add $w$ to $V_{lev}^{new}$.

  5. If $u \in V_{lev}^{new}$ then return $f(u)$ as the shortest path length.
  6. Set $V_{lev} = V_{lev}^{new}$ and go to 4.

The idea is the following: Instead of sorting the edges by weight, we iterate over them in any order and update the weight label of the node the edge goes to whenever needed. Since each edge is considered at most twice (in each direction) the total complexity is linear in $\lvert E \rvert$.

$\endgroup$

You must log in to answer this question.

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