Find the shortest distance path in a weighted graph, where the weight of each edge is non-negative and less than a constant C = 500 in linear time

Question

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.

Answer 1

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