0
$\begingroup$

The problem is to find the shortest distance in a weighted graph, where the weight of each edge is non-negative and it is given that the weight of each edge is less than a constant C. For example, C = 500.

I know that I can solve this problem using Dijkstra, however, the time complexity would be high. The problem should be solved in linear time in terms of the vertices and edges of the graph.

I think this has to do with some linear graph traversal, BFS or DFS

A direction would be appreciated on how to solve this problem in linear time.

$\endgroup$

1 Answer 1

1
$\begingroup$

Algorithm:

  1. Build a new graph $G' = (V', E')$, where for every edge $e = (u,v) \in E$ with weight $w(e) > 1$:

    Replace the edge by a path P (simple) of length $w(e)$, where each edge in path $P$ has weight of 1. Meaning, path $P$ will have $w(e)-1$ nodes and $w(e)$ edges. $P = (u, x_1, x_2,..,x_{w(e)}, v)$

  2. Run BFS on the new graph $G'$.

  • Time Complexity:

Let's look at $G' = (V', E')$.

At most, our new graph has at most $C\times|E|$ vertices and $C\times|V|$ edges. Thus, the time complexity linear in terms of $G=(V,E)$, since BFS requires a linear time complexity.

  • Proof of correctness:

It is enough to prove that our new graph $G'$ is equivalent to our original graph $G$. That means, for each two nodes $(u,v)$ which had a path between them, there still exists a path between them with the same weight as in our original graph $G$. By proving this, you would've also proved that for every node $v$ which was reachable from node $u$ in $G$, the node $v$ is still reachable from node $u$ in our new graph $G'$.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you for the answer. For the proof, I showed that since we replaced each edge with a simple path then we v is still reachable from u. $\endgroup$
    – Mikey
    Commented Feb 7, 2023 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.