的建議某些圖形操作

Question

該項目的最後期限正在接近非常迅速，我沒有太多的時間來處理它所剩下的最簡單的算法。因此，我正在尋找最簡單的算法來在Graph結構上實現一些操作，而不是尋找最好的（也許更復雜/更耗時的）算法。

我需要做的操作如下：

• 列表圖形網絡中的所有用戶給出的距離X
• 列表圖形網絡中的所有用戶給出的距離X和類型關係的
• 計算給定類型關係
• 計算圖表網絡
• 計算MO 2個用戶之間的最大距離的圖表網絡上的用戶之間的最短路徑圖表網絡

關於我的圖形實施的幾點注意事項對ST遙遠連接的用戶：

• 邊緣節點具有2個屬性，一個是char類型和另一int的。它們分別代表關係和重量的類型。
• 圖是用鏈表實現，頂點和邊兩者。我的意思是，每個頂點指向下一個頂點，並且每個頂點也指向不同鏈接列表的頂點，即該特定頂點的邊。

我知道什麼，我需要做的：

• 我不知道這是最簡單的，因爲我上面說的，但是對於用戶之間的最短路徑，我相信，Dijkstra算法算法是人們似乎經常推薦的方法，所以我認爲我會這樣做。
  • 我一直在尋找和搜索，我發現很難實現這個算法，有誰知道任何教程或易於理解的東西，所以我可以自己實現這個算法？如果可能的話，用C源代碼的例子，這將有很大的幫助。我看到很多數學符號的例子，但是這更令我困惑。
  • 你認爲這將有助於如果我「轉化」的圖形，以鄰接矩陣來表示的鏈接權重和關係類型？執行該算法而不是鏈接列表會更容易嗎？我可以輕鬆實現一個功能，在需要時進行轉換。我這樣說是因爲在閱讀了關於這個主題的幾頁後，我感覺它會更容易些，但我可能是錯的。
• 我沒有對其他4個操作，建議任何想法？

Answer 1

列表圖形網絡中的所有用戶給出的距離X

從什麼的距離X？從一個起始節點或距離X之間？你能給個例子嗎？這可能會也可能不會像進行BF搜索或運行Dijkstra一樣簡單。

假設您從某個節點開始，並且想要列出所有距離爲X的節點到起始節點，只需從起始節點運行BFS即可。當您要在隊列中插入一個新節點時，請檢查從起始節點到要插入新節點的節點的距離+要插入新節點的節點的邊的權重新節點是< = X。如果嚴格低於，則插入新節點，如果相等，則僅打印新節點（並且只有在您也可以將0作爲邊權重時才插入）。

列表給出一個距離X的圖表網絡中的所有用戶和

見上述關係的類型。只要考慮到BFS中的關係類型：如果父類型與嘗試插入隊列的節點的類型不同，請不要插入它。

計算給定類型關係的圖表中網絡上的用戶之間的最短路徑

算法取決於多種因素：

• 多久，你將需要計算這個？
• 你有多少個節點？

既然你想要簡單，最簡單的是Roy-Floyd和Dijkstra's。

• 使用Roy-Floyd在節點數量上是立方的，所以效率很低。如果您可以負擔運行一次，然後回答O（1）中的每個查詢，請僅使用此值。如果你有能力在內存中保留一個鄰接矩陣，請使用它。
• 如果要保持簡單，Dijkstra的節點數量是二次的，但每次要計算兩個節點之間的距離時都必須運行該節點。如果您想使用Dijkstra's，請使用鄰接列表。

這裏是C實現：Roy-Floyd和Dijkstra_1,Dijkstra_2。您可以通過"<algorithm name> c implementation"在google上找到很多信息。

編輯：對於18000個節點，Roy-Floyd不存在問題，因爲它是一個鄰接矩陣。這將花費太多的時間來構建和過多的內存。最好的辦法是對每個查詢使用Dijkstra算法，但最好是使用堆來實現Dijkstra - 在我提供的鏈接中，使用堆來找到最小值。如果你在每個查詢上運行經典的Dijkstra，那也可能需要很長時間。

另一個選擇是在每個查詢上使用Bellman-Ford算法，這會爲每個查詢提供O(Nodes*Edges)運行時間。然而，如果你沒有像維基百科告訴你的那樣執行它，這是一個高估。相反，使用類似於BFS中使用的隊列。每當節點更新其與源的距離時，將該節點重新插入到隊列中。這在實踐中將會非常快，並且也會對負權重起作用。我建議你使用這個或Dijkstra堆，因爲古典Dijkstra可能需要很長時間在18 000個節點上。

計算圖形網絡

最簡單的方法是使用回溯2個用戶之間的最大距離：嘗試所有的可能性，並保持發現的最長路徑。 This is NP-complete，所以不存在多項式解。

如果您有18 000個節點，我不知道任何算法（簡單或其他），對於如此之多的節點可以合理快速地工作。考慮使用貪婪算法對其進行近似。或者也許你的圖有一些你可以利用的特性。例如，它是否是DAG（有向無環圖）？

計算圖形網絡

這意味着你要查找的圖的直徑上最遙遠的連接的用戶。最簡單的方法是找到每個兩個節點之間的距離（所有節點都配對最短路徑 - 在每兩個節點之間運行Roy-Floyd或Dijkstra並以最大距離選擇兩個節點）。

同樣，這對於節點數和邊數很難做到。恐怕在最後兩個問題上你的運氣不好，除非你的圖有特殊的屬性可以被利用。

如果我將圖轉化爲鄰接矩陣來表示鏈接權重和關係類型，您認爲這會有所幫助嗎？執行該算法而不是鏈接列表會更容易嗎？我可以輕鬆實現一個功能，在需要時進行轉換。我這樣說是因爲在閱讀了關於這個主題的幾頁後，我感覺它會更容易些，但我可能是錯的。

不，鄰接矩陣和Roy-Floyd是一個非常糟糕的主意，除非您的應用程序針對超級計算機。

Answer 2

這個假設O(E log V)是一個可以接受的運行時間，如果你在網上做某些事情，這可能不是，它可能需要一些更高性能的機器。

• 列表圖形網絡中的所有用戶給出的距離X

Djikstra's algorithm好這一點，對於一次性使用。您可以保存結果以供將來使用，並可對所有頂點進行線性掃描（或更好地進行排序和二進制搜索）。

• 列表中給出的距離X和

可能是幾乎一樣的上述關係的類型的圖形網絡中的所有用戶 - 只需使用一些功能，其中的權重將是無窮大，如果它是不是正確的關係。

• 計算給定類型的關係

與上述相同的圖形網絡上的用戶之間的最短路徑，本質上，只是早確定是否這兩個用戶相匹配。 （或者，您也可以「在中間相遇」，而提前終止，如果你發現在兩個最短路徑生成樹某人）

• 計算圖形網絡

Longest path 2個用戶之間的最大距離是NP-complete problem。

• 計算圖表網絡

上最遠的連接的用戶這是曲線圖，它可以在Math World閱讀有關的直徑。

至於鄰接列表vs鄰接矩陣問題，取決於你的圖是多麼密集。另外，如果你想緩存結果，那麼矩陣可能是要走的路。

Answer 3

計算兩個節點之間最短路徑的最簡單算法是Floyd-Warshall。它只是三重嵌套循環;而已。

它計算ALL -pairs在O(N^3)最短路徑，因此它可以做更多的工作不是必要的，並且將需要一段時間，如果N是巨大的。