我該如何解決這個問題？

給定一個無向加權圖G =（V，E）。每個頂點代表一個城市，連接a和b的邊的權重是完成在城市a和城市b之間建立高速路線所需的年數。描述一個算法，可以在圖表中的任意兩個城市之間旅行之前找到最少的年數。這些路線是同時建立的，所以如果我們有三個城市a，b和c以及a和b之間的權重爲1的邊，b和c之間的另一個邊的權重爲2，那麼輸出應該是2.我該如何解決這個問題？

來源

2012-06-01 Aden Dong

你試過了什麼？提示：http://en.wikipedia.org/wiki/Kruskal%27s_algorithm – nhahtdh

會簡單地使用prim或kruskal來找到最小生成樹，然後返回mst工作中所有邊的最大權重？如果是這樣，你將如何去證明算法的正確性？ –

對於Kruskal來說，證明非常簡單，因爲在添加時你總是首先考慮最小邊緣。我對Prim並不確定，但它可能是可以證明的。 – nhahtdh

上面的評論指出你正確的答案，在我看來這聽起來像是一個經典的Prim算法問題。 http://en.wikipedia.org/wiki/Prim's_algorithm

來源

2012-06-01 02:28:56

那是怎麼回事？你能更具體嗎？例如，只需使用prim來找到最小生成樹，然後返回mst工作中所有邊的最大權重？如果是這樣，你將如何去證明算法的正確性？ –

@AdenDong我會像你說的那樣去做。如果鐵路的建設全部同時進行，那麼最小生成樹將在數學上爲您提供連接網絡中所有節點的最佳路由。 A和B之間的路徑中兩個頂點之間最長的弧線應該是您需要等待多少行程。 –

我該如何解決這個問題？

回答

相關問題