非加權圖中鄰接列表中的最短路徑

首先，我想確保我得到了正確的結構。據我所知，表示的曲線圖的鄰接表看起來像這樣：非加權圖中鄰接列表中的最短路徑

an adjacent list

AdjList是一個ArrayList，其中每個元素是一個對象。每個對象都包含一個ArrayList來表示連接的頂點。因此，例如，在上面的圖像中，Vertext 1（AdjList中的第一個索引）連接到AdjList的索引2,4和5處的頂點。這種鄰接表的表示是否正確？（ps：我知道索引從0開始，爲了簡單起見，我在這裏放1）。

如果它是正確的，我應該使用哪種算法來找到兩個頂點之間的最短路徑？

來源

2011-12-17 sqram

一起在Java Dijkstra's shortest path算法的例子有沒有算法給你只有兩個頂點之間的最短路徑。您可以使用：

Dijkstra's algorithm找到一個頂點和所有其它的（然後選擇一個你需要的）之間的最短路徑。
Roy-Floyd algorithm找到所有可能的頂點對之間的最短路徑。

鏈接還包括僞代碼。

來源

2011-12-17 19:52:13 Tudor

對於未加權圖Dijkstra是一個矯枉過正。您可以使用BFS，並在您到達目的地的第一時間停止。 – niteria 2011-12-17 21:10:56

此外，閱讀Dijkstra的alg，它似乎像圖必須加權？ – sqram 2011-12-17 23:19:50

@lyrae：如果圖形是非加權的，你可以簡單地將所有權重設置爲1。 – Tudor 2011-12-17 23:23:58

下面是與解釋

來源

2011-12-17 19:52:01

您可以使用Dijkstra's和Floyd Warshall。對於未加權的圖，假定每個邊的權重爲1並應用該算法。

來源

2012-07-11 08:12:39

非加權圖中鄰接列表中的最短路徑

回答

相關問題