2
$\begingroup$

I found the following problem in my textbook and I'm having trouble with coming up with a solution. I'm thinking maybe there's a way to improve Dijkstra's algorithm by using a data structure other than a priority queue, since that's what causes the log(n) time complexity, but I'm a bit lost. Here's the question:

Suppose you are given a connected weighted undirected graph, G, with n vertices and m edges, such that the weight of each edge in G is an integer in the interval [1, c], for a fixed constant c > 0. Show how to solve the single-source shortest-paths problem, for any given vertex v, in G, in time O(n + m).

Hint: Think about how to exploit the fact that the distance from v to any other vertex in G can be at most O(cn) = O(n).

The "single-source shortest-paths" problem, is a problem in which we are given one vertex along with several nodes in a graph, and we are required to find the shortest path to any other node, given the edge length between each node.

I really appreciate any help in advance!

Improve this question
$\endgroup$
2
  • $\begingroup$ Think about why you need a priority queue in Dijkstra's algorithm. You need to be able to extract the node with the minimum distance from all the vertices inside the "frontier". Now that you know that each of these vertices can be at most c distance from any vertex, can you perhaps have an array of size c that stores which nodes are at what distances, and every time you need to extract the minimum, you would loop over this array in O(c)=O(1) time. Does this give you enough ideas? $\endgroup$
    – AspiringMat
    Apr 10, 2018 at 5:41
  • $\begingroup$ To make this a bit more clearer, you would have an array of linked lists. array[i] is a linked list with all the elements that are at distance i from the closes vertex inside the "frontier" $\endgroup$
    – AspiringMat
    Apr 10, 2018 at 5:44

1 Answer 1

Reset to default
6
$\begingroup$

There are many ways to solve this problem in linear time. I'll write the one I found easiest to understand.

The main idea is to transform the weighted graph into an unweighted one. If the number of nodes and edges of the transformed graph remains linear to $n$ and $m$, then we can run BFS to solve it in $O(n+m)$.

The transformation is as follows: for each edge $(u,v)$ of weight $w$, create $w-1$ nodes to connect $u,v$. For example an edge $(a,b)$ of length $3$, we create two dummy nodes and transform it into

$a-d_1-d_2-b$

It is easy to check that this transformation preserves the shortest path between any pairs of nodes. The number of nodes is now $O(n+cm)=O(n+m)$ and the number of edges is $O(m+cm)=O(m)$. Since BFS is linear to the number of nodes and edges, we have a runtime of $O(n+m+m)=O(n+m)$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @Dominic if this answer helped you, can you mark it as accepted? $\endgroup$
    – Christopher Boo
    Apr 26, 2018 at 13:47

Your Answer

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

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