尋找加權無向圖中固定成本的路徑？

Question

我有以下問題，我不太清楚如何解決這個問題：

給定圖G = (V;E)其中每一條邊有一個正整數成本c_e和起始頂點s\in V。設計一個O(V + E)算法，使用路徑（不一定是簡單的路徑）與路徑總成本的5

是倍數可達標誌着所有頂點從s我怎麼可以跟蹤的成本總額的我已經訪問過的路徑？我一直在研究有向圖中的BFS，並在這裏嘗試了一些嘗試，但大多數BFS參考文獻的重點是找到最短路徑（而不是像保持5的倍數）。

Answer 1

你對下一個算法有什麼看法？

讓我們考慮基於源圖的新有向圖。對於來自源圖的每個頂點v在新圖中創建5新頂點v[0], v[1], ..., v[4]對應於除以5的劃分的模塊。然後，如果頂點v和u在源圖中由權重爲w的邊連接，則在新圖中添加v[i]和u[(i + w) % 5],u[j]和v[(j + w) % 5]之間的邊，其中i = 0..4, j = 0..4。然後從v[0]運行BFS，其中v是源圖中的起始頂點。

考慮頂點與索引0像v[0]。它們中的每一個對應於源圖中的頂點v的長度倍數5的路徑。從起始頂點到達答案的所有這些頂點標記在BFS之後。總的複雜性是線性的。