點之間最簡單的路徑

我有一個點（x，y座標）列表和它們之間的連接列表。實例：點之間最簡單的路徑

點甲乙 Ç d Ë

聯繫 AB BC CE BD

D E 
    | | 
A-B-C

當然，也有許多更多的點，比此連接。 ..

我需要什麼d o找出這些點之間最簡單的路徑。例如，如果我想去A，C和D，我想使用AB，BC和BD連接。

有沒有一種方法來計算我想要連接的任何一組點？

來源

2010-02-09 s2lk3n42lk34

最簡單的是一個有點武斷的術語。你最簡單的意思是什麼？ – 2010-02-09 21:53:40

由於您沒有指出與邊緣相關的任何費用，因此Breadth First Search可能就是您要查找的內容。它找到從給定節點到所有其他節點（如果存在）的最短路徑，我假設這就是'最簡單'的含義。

來源

2010-02-10 09:31:13 MAK

@Phil：請重讀一本好書的圖遍歷章節（嘗試CLRS）。 BFS保證在未加權的圖中返回最短路徑，但DFS只能找到任何路徑，不一定是最短路徑。閱讀這個證明。此外，在一個未加權的圖中，所有的邊緣成本通常被假定爲1.如果所有成本都是0，那麼'最短'路徑的概念是沒有意義的（所有路徑的成本都是0）。但是，也許你的問題需要成本爲0，出於某種原因，在這種情況下，你應該編輯你的問題，並確定'最簡單'的含義。 – MAK 2010-02-10 17:30:11

你說得對。我犯了一個錯誤。我拿出我的答案給你+1。 – Phil 2010-02-11 17:21:50

點之間最簡單的路徑

回答

相關問題