尋找包含兩個節點的最短週期

Question

設G =（E，V）爲一個有非負邊緣代價的有向圖。讓s爲頂點。我需要找到一個算法，每個頂點v，包含s和v的最短週期。循環可能包含幾次相同的邊緣。

有意義的解決方案是從s運行Dijkstra以便找到從s到每個v的最短路徑。然後，從每個v再次運行Dijkstra以便找到從v到s的最短路徑。最短的週期是兩者的結合。

這個工作，但將採取O（| V || E | + | V |^2 *日誌| V |）。有更好的解決方案嗎？

Answer 1

對於有向圖，您可以使用Floyd-Warshall Algorithm找到所有兩對之間的最短路徑。

或者更有效的解決辦法是在反轉圖形運行Dijsktra（G'=(V,E')，使得對於在每E(v,u)，(u,v)是在E'）和CONCAT兩個溶液（一個在當然反向）。 這基本上是運行Dijkstra兩次。