algorithm - 给定一个加权图和自然数 k，如何找到可以除以 k 的从节点 s 到 t 的最便宜的路径？

Question

给定一个不包括负循环的加权图 G=(V,E)、一个自然数 k 和两个顶点：s,t。

我怎样才能找到从 s 到 t 的最便宜的路线，它的长度可以被 k 整除？

标签： algorithmshortest-pathdijkstrabellman-fordweighted-graph

Answer 1

准备一个具有顶点 V × {0, 1, ..., n−1} 的新图 G'，并且对于 G 中长度为 ℓ 的每个弧 v → w，弧 (v, x) → (w, (x + ℓ) mod k)。然后使用 Dijkstra 算法找到从 (s, 0) 到 (t, 0) 的最短路径。