Given a weighted graph and natural number k how to find the cheapest path from node s to t that can be divided by k?

Question

Given a weighted graph G=(V,E) which doesnt include negative cycles, a natural number k, and two verticles: s,t.

How can I find the cheapest route from s to t which its length can be divied by k?

Answer 1

Prepare a new graph G' with vertices V × {0, 1, …, n−1} and for each arc v → w of length ℓ in G, arcs (v, x) → (w, (x + ℓ) mod k). Then use Dijkstra's algorithm to find a shortest path from (s, 0) to (t, 0).