C＃圖最短路徑算法

Question

這是我的問題。我有一系列建築物不同部分的照片，我需要將它們連接在一起。之後，我需要按順序顯示每張照片，以顯示從A點到B點的路徑......即，從教室到火災逃生。

我已經做了一些研究，並且我相信一個非定向的未加權圖應該可以做到。

因爲我在這方面沒有太多的經驗。我想知道如何將照片存儲在數據結構中，以及是否有任何圖書館可以完成這項工作？

Answer 1

是的，你需要應用一些算法，可以爲你解決問題。

你可以使用這個偉大的libray：

• QuickGraph

解決這個問題的一部分。關於存儲數據的方式，您需要定義頂點（照片）和頂點之間的邊緣，如（照片A-photoB），（照片A-photo C）等等。

您必須從數據庫中恢復該信息，並在quickgraph中加載相應的結構，並讓它爲您找到路徑。

這裏有大量的文檔和示例：

• Quick graph documentation

類似，對於這個我用過的東西：

• MyEdges類，它實現IEdge<T>（T應該是你照片ID類型，int或其他） - 代表照片之間的邊緣（地點）
• 圖類，繼承AdjacencyGraph<T,MyRelation>。你可用MyEdges加載（這是有向圖）
• 路徑查找器算法類：我從FloydWarshallAllShortestPathAlgorithm<T, MyRelation>

然後繼承你必須：

• 創建邊緣（即從閱讀DB）
• 實例a圖形類，並向其添加所有邊線
• 使用路徑查找器構造函數，使用圖形作爲參數。這找到了路徑。

該算法可以讓你指定你可以從一個給定的照片（邊）去哪些照片，假定該距離是它們之間的相似，但你必須定義所有路線（從A到B，的B到A等）。這是OP的「未加權」部分。如果你的情況不同，你將不得不閱讀文檔。

如果您更喜歡添加A到B也將B添加到A，則可以實施UnDirected圖。它可以省掉一些代碼行，但我通常更喜歡自己添加所有的可能性。 「從圖書館我可以去過道A和過道B，從過道B到圖書館和實驗室」等等，這更容易想到，試圖想到所有的邊緣。

您可以在數據庫中創建兩個表：

• 照片（使用標識）
• 路徑（IdFrom和IdTo）

這是易於維護和實現。