Compute single-source shortest paths in O(n+m) time? 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 &gt; 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 &quot;single-source shortest-paths&quot; 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!
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)$.