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.