將循環圖分解爲最短路徑子圖的最小數目

給定一個循環圖，我正在尋找一個將此圖分解爲非循環子圖的算法。這些子圖中的每一個都有一個根頂點，這個頂點是計算最短路徑的源。例如，下面給出的循環圖，其中，所述週期是3,4之間，和5：將循環圖分解爲最短路徑子圖的最小數目

     +-------------------------+ 
         |       | 
         |       | 
      +----------+----------+    | 
      v   |   v    | 
+---+  +---+  +---+  +---+  +---+ | 
| 1 | --> | 3 | <--> | 4 | <--> | 5 | --> | 6 | | 
+---+  +---+  +---+  +---+  +---+ | 
        ^      | 
         |       | 
         |       | 
        +---+      | 
        | 2 |      | 
        +---+      | 
        +---+      | 
        | 7 | <---------------------+ 
        +---+

相對於最短路徑的子圖1是：

+---+  +---+  +---+  +---+ 
| 1 | --> | 3 | --> | 4 | --> | 7 | 
+---+  +---+  +---+  +---+ 
      | 
      | 
      v 
      +---+  +---+ 
      | 5 | --> | 6 | 
      +---+  +---+

最短路徑的子圖相對於2將是：

  +---+ 
      | 7 | 
      +---+ 
      ^
      | 
      | 
+---+  +---+  +---+  +---+ 
| 2 | --> | 4 | --> | 5 | --> | 6 | 
+---+  +---+  +---+  +---+ 
      | 
      | 
      v 
      +---+ 
      | 3 | 
      +---+

相對於最短路徑sugraph至5將是：

+---+  +---+  +---+  +---+ 
| 6 | <-- | 5 | --> | 4 | --> | 7 | 
+---+  +---+  +---+  +---+ 
      | 
      | 
      v 
      +---+ 
      | 3 | 
      +---+

注意，關於3的最短路徑子圖是1的子集，4是2的子集。 6和7是葉子。

我目前的（天真的）解決方案將是爲每個節點執行一個BFS，標記節點訪問以防止週期。然後檢查子圖是否是彼此的子集以創建最小數量的不同子圖。任何更好，更正式的解決方案的想法？

編輯在我的情況圖是不加權的，但有後人的一般解決方案是很好的。

（與http://bloodgate.com/graph-demo由圖）

來源

2011-08-25 tgoodhart

templatetypedef，OP使用「BFS」表示該圖未加權。

下面是一個算法，該算法的運行時間與最終集合中每個根的總和成正比，該總和可以從該根可訪問的子圖的大小。例如，對於有界度數的圖，這與輸出大小的順序有關。

爲了唯一性，我將假定「最短路徑」意味着長度最小的序列。在高層次上，我們計算處理頂點的順序，以便如果頂點u的BFS樹包含頂點v，則u在v之前排序。每個頂點都在線性時間內處理，包括確定它包含的頂點。

通過查找強組分，拓撲排序強組分，然後任意排序每個單一組分中的頂點來計算順序。顯然，只有從u到達的頂點集合是從v到達的頂點的適當超集，u才包含v。

要處理頂點u，從u計算BFS樹，然後確定子樹具有的頂點集沒有電弧離開子樹 - 這些是包容的。通過遍歷樹深度優先來確定後者，爲每個頂點v記錄其左端點是輸入時間並且其右端點是退出時間的間隔I（v）。對於每個頂點v，用弧v-> w計算包含I（v）和I（w）的最小間隔J（v）。使用DFS，爲每個頂點v計算v的所有後代w的包含K（w）的最小間隔K（v）。當且僅當K（v）= I（v）。

爲什麼要這樣工作？我們知道，植根於u的樹的v子樹是植根於v的樹的子集。假設u包含v（換句話說，這兩棵樹相等）。然後，顯然v的子樹中每個弧的頭部都會到v的子樹，否則頭應該被探索。相反，假設你不包含v。以v爲根的樹包含一個不在v的子樹中的頂點，因此有一個弧離開v的子樹。

我希望這個描述對你有用，但是我擔心你的實際問題涉及到具有次級空間的快速點對點最短路徑查詢，爲此可能會有更好的方法。

來源

2011-08-25 20:59:38 comestibles

@食譜 - 我發現一篇論文，有人想出了一個非常快的APSP算法，並將其添加到我的答案中。另外，我對你的算法有點懷疑，因爲我不認爲你的「包含」的定義必然是正確的。僅僅因爲你可以達到與v相同的一組頂點，並不意味着v中的BFS樹將被包含在U的BFS樹中。或者我錯了嗎？ – templatetypedef

@templatetypedef我說：「顯然你只包含v_only if_ ...」，不是當且僅當。換句話說，可能有從u到v的路徑，但是u不包含v。在第二階段中將誤報消除。另外，您鏈接的論文是關於節省時間的;如果OP仍然願意運行所有的BFS，那麼似乎時間不是問題，但只有OP可以肯定地告訴我們。 – comestibles

@食品 - 啊，我的錯誤，我誤解了。回顧一下，看起來在最糟糕的情況下，你需要運行O（n）不同的BFS迭代，這會得到O（n（n + m））= O（n^2 + nm）的運行時間，，其中m = o（n log n）的圖比迭代的Dijkstra更好，對於m = o（n^2）的圖更好於Floyd-Warshall。非常好！ – templatetypedef

每次你上面列出的被稱爲shortest path tree要找到一些頂點爲根的單一最短路徑樹，你可以使用Dijkstra算法的樹木，這兩者的發現從源節點到每個其他節點的最短路徑，並顯示使用哪條邊到達這些節點。這會立即爲您提供單個節點的最短路徑樹，假定該圖不包含任何負邊。如果你想列出所有的樹，你可以通過從每個節點開始運行Dijkstra算法來實現。給定一個斐波那契堆，它運行在O（VE + V log V），它非常快。

如果您沒有斐波納契堆，或者使用密集圖形，或者可能有負循環，則可能需要使用Floyd-Warshall算法。該算法在時間O（V ）中運行並且針對每個節點計算到每個其他節點的最短路徑，即使存在負邊緣也是如此。從這裏，你可以很容易地恢復所有的最短路徑樹。

希望這會有所幫助！（M（n）log n），其中M（n）是乘法所需的時間小數字矩陣在一起。由於這可以很快地完成（大約O（n ^2.3），這將是解決問題的最佳算法。有一篇關於算法here的文章，但它位於付費牆之後，實際上，處理真正巨大的圖（比方說，數以萬計的節點）我不認爲你需要擔心使用這個更強大的算法，但它仍然是很好的瞭解。

來源

2011-08-25 19:43:22 templatetypedef

謝謝！我相信，如果我考慮這些子圖的每一個的邊集，並解決http://en.wikipedia.org/wiki/Set_cover_problem，我會得到我正在尋找的東西。 – tgoodhart

將循環圖分解爲最短路徑子圖的最小數目

回答

相關問題