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?
Asked
Active
Viewed 476 times
3
-
Are (non-negative) path cycles allowed? – tucuxi Dec 09 '20 at 13:12
-
@tucuxi yes, thanks for your time. – cstudent1212 Dec 09 '20 at 13:14
2 Answers
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).
David Eisenstat
- 64,237
- 7
- 60
- 120
0
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.
tucuxi
- 17,561
- 2
- 43
- 74