Q

圖表：尋找具有最小重量路徑，通過n條邊？

2017-03-31 41 views -1 likes

-1

鑑於無向，加權圖，我需要找到從頂點A到頂點B的路徑與n條邊的最小總重量。圖表：尋找具有最小重量路徑，通過n條邊？

我發現關於「最寬的路徑問題」維基百科文章和我的問題看起來相似，但我怎麼能延長該算法幾個邊？

有另一種算法，有人可以建議？

2017-03-31 user3365834

+0

多少個節點你在最壞的情況下呢？ –

A

回答

0

1）解決問題的一個最大優勢

2）刪除此邊緣和合並其頂點

3）重複，直到你有邊緣的所需數量

2017-03-31 23:47:37 BartoszKP

+0

的問題是，我有幾個疑問，不能修改圖表。 – user3365834

+0

@ user3365834我不知道什麼是「查詢」是在這方面。您不需要修改圖形，創建另一個具有此差異的圖形。或者創建一個代理，它可以傳遞關於圖的所有原始信息，但只需要修改一次。到合併的頂點。無論如何，這些問題在算法層面進行交流時是無關緊要的。 – BartoszKP

相關問題