Can somebody can help me with this problem:
I have to calculate the minimum distance from a source node $s$ for undirected and connected graphs $G = ( V, E)$ with weights on the arcs belonging to the set $\{ 1, 2, . . . , k \}$, where $k$ is a fixed integer.
Implement Dijkstra's algorithm taking advantage of the peculiarity of these graphs so that the minimum distances to be calculated in $O ( k | V | + | E |)$.
I've no idea how to solve this problem. I don't need the specific code , but I need an algorithmic idea . Thanks in advance :)
Hint: Use an array / list that you can do random access on as the priority queue instead of using a binary tree.
More hint: Suppose you have a super large array $q$. Now, whenever you "push" a value $i$ into the queue, place it into $q[i]$. Instead of popping the queue, you loop the queue from the smallest to largest index.