檢查從頂點v到另一個頂點w的所有路徑是否具有相同的長度

Question

我有一個連接圖g和n頂點和m邊。

每條邊都可以從兩個方向穿過，而在一個方向上穿過它們的重量是正的，在另一個方向穿過它們並且它們的重量是負的。

因此，對於每一個邊緣u - >v體重w存在一個邊緣v - >u體重-w。

我的目標：

對於給定的頂點v，檢查是否存在一個路徑回v（一個週期），因此該路徑的邊緣權重的總和不等於0。如果存在這樣的路徑，則輸出該路徑的最小數量的邊緣，否則輸出"all cycles are fine"。

實例：

一個例子，其中從v到v總和的所有路徑可達0。輸出爲"all cycles are fine"：

在存在路徑從v到v其邊緣總結到的東西是不等於0一個例子。這樣的路徑的邊的最小數目是4在該實例中：

我目前的做法：

這個問題似乎是等效於檢查是否從一給定頂點v所有路徑到任何其他頂點w的長度相等，如果這是真的，那麼「所有周期都很好」，否則我輸出打破條件的最短週期的長度。我無法找到一個有效的算法來測試這種情況。

Answer 1

檢查是否存在通過頂點A的「錯誤週期」的簡單算法是從A運行BFS，然後查看哪些頂點B至少以不同成本訪問過兩次。如果沒有B存在，那麼所有的週期都是好的，否則就會有一個不好的週期（邊緣直到第一次訪問B）+（邊緣直到以不同的成本訪問B）。這個BFS最多訪問每個頂點兩次，所以複雜度仍然是線性的。

因此，這個問題可以用圖中每個頂點的BFS來解決。當然，也許這可以提高效率;什麼是足夠的取決於n和m的大小。