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

Use BFS with a priority queue, so as to always examine states (= paths from s) that are shortest. Unlike normal Dijkstra, your states are full paths, and you can revisit already-visited vertices as often as they are encountered.

I cannot prove that such an algorithm would be optimal, but at least it should be correct, always returning a valid shortest-path answer if it exists. Runtime for certain graphs and values of K would be very high, and the algorithm may not finish at all if there are no k-divisible paths from s to t but there are loops with a path-length divisible by k. You could find and filter those out first by using a preliminary DFS.

Answer 2

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).