未加權圖/樹中兩個給定節點之間的最短路徑

我正在尋找一種算法，以通過使用鄰接矩陣來確定未加權圖中兩個節點之間的最短路徑。我知道迪克斯特拉和貝爾曼 - 福特，但沒有發現特定的確定兩個給定節點之間的最短路徑。未加權圖/樹中兩個給定節點之間的最短路徑

任何幫助是極大apreciated

2013-04-05 Dorin Rusu

這個問題可能是如此的一般/理論，以便在cs.stackexchange.com上得到更好的回答。查看圖形標籤：http://cs.stackexchange.com/questions/tagged/graphs – 2013-04-05 16:00:37

[使用Dijkstra算法找到鄰接矩陣中的最短路徑]的可能重複（http://stackoverflow.com/questions/8379866/使用-的Dijkstra算法找到的-最短路徑在-AN-鄰接矩陣）。另外，[本文]（http://www.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides14.pdf）描述瞭如何使用矩陣乘法計算最短路徑。 – 2013-04-05 16:01:37

出於好奇，爲什麼你認爲Dijkstra算法和Bellman-Ford不能用於找到兩個節點之間的最短路徑？ – templatetypedef 2013-04-05 16:59:38

一個簡單的選擇是，直到第二個節點發現運行廣度優先搜索從第一個節點。如果您爲每個節點存儲父指針，則可以讀取從第一個節點到第二個節點的路徑。而且，這在圖的大小上以線性時間運行。

希望這會有所幫助！

來源

2013-04-05 16:04:39 templatetypedef

這是一個非常好的主意。非常感謝你！ – 2013-04-05 16:05:24

它工作得很好，再次感謝你！ – 2013-04-09 16:27:03

未加權圖/樹中兩個給定節點之間的最短路徑

回答

相關問題