要確定是否有兩個點之間使用C++或C

Question

路徑我有一個無向圖表示由鄰接矩陣。

我需要一個高效率的代碼，該函數只需要返回true或false。

而且我知道Dijkstra's algorithm可以工作，我想我並不需要的最短路徑，而我的鄰接矩陣是：

a[i][j] = 1 or -1 

有沒有其他的值。

Answer 1

對不起，我沒有注意到你的矩陣僅包含0和1

如果只查詢一次，也許DFS或BFS是更好的，只有O(|V|+|E|)

如果是雙向路徑，Disjoint-set data structure（See wikipedia ） 是有效的！

• 單源或多源？
• 單查詢或多查詢？

如果只有一個查詢，則所有單源最短路徑算法都可以。像：

• 貝爾曼 - 福特O(|V||E|)
• 的Dijkstra O(|V|^2)
• Dijkstra算法+堆Θ((|E|+|V|)log|V|)
• SPFA（貝爾曼 - 福特使用隊列）
• ...

如果有很多查詢，請考慮

• 弗洛伊德 - Warshall算法O(|V|^3)

Answer 2

如果你只需要知道兩個點是否連接與否，我認爲http://en.wikipedia.org/wiki/Disjoint-set_data_structure會以最快的速度，你可以做希望有關工作。從它自己的集合中的每個點開始，然後，對於兩個點之間的每個鏈接，加入這些點所屬的兩個集合。