發現節點之間的最短路徑，以及圖形是否連接

明顯在下面是一個作業問題。我無法理解我的教授在說什麼，所以我甚至不需要知道從哪裏開始尋找找到這個問題答案所需的信息。如果你能給我一些關於在哪裏學習這些東西的線索，以及你如何解決這個問題，我會很感激。發現節點之間的最短路徑，以及圖形是否連接

在下圖中，找到兩個節點之間的最短路徑 - 您的選擇，但讓問題變得有趣。

這是一個連接圖嗎？

enter image description here

我會讀我的筆記。 – 2013-03-04 19:50:21

@SotiriosDelimanolis說實話，我很少發現我的講稿很有用。大多數情況下，我使用在線教程或YouTube視頻來擴展筆記中的主題，因爲大多數情況下他們只是演講者在演講中所說的內容的摘要。 – 2013-03-04 19:51:55

另外谷歌的'圖最短路徑'並閱讀一些搜索結果。 – 2013-03-04 19:52:06

這將會是最好先了解圖表如何在內存中表示連接你可以告訴。如果取決於你，你可以使用二維數組，因爲這是表示加權邊的最簡單方法。

最簡單的實現最短路徑算法可能是Djikstra的，稍慢但比A *複雜。要使用Djikastra，您需要首先實現優先隊列。在Java中有一個PriorityQueue類，否則你必須自己實現它。之後，使用維基百科或其他地方提供的僞代碼，實現應該相當簡單。

2013-03-04 20:29:27

你應該使用星算法來找到兩個節點之間的最短路徑。 http://en.wikipedia.org/wiki/A_star

2013-03-04 19:50:10 75inchpianist

回答