我该如何解决这个问题？

给定一个无向加权图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之间的路径中两个顶点之间最长的弧线应该是您需要等待多少行程。 –

我该如何解决这个问题？

回答

相关问题