医院选址问题 高手请进
医院选址
问题描述：有n个村庄，现要从这n个村庄中选择一个村庄新建一所医院，使其余的村庄到这所医院的距离总体来说较短，设计较合理。
实现要求：可以将问题抽象为有n个接点，在这n个接点之间建立一个无向图，边上的权值w(i,j)表示村庄i到j之间道路的长度， 在无向图中n个顶点之间，最多可能设置n(n-1)/2条线路，如何在这些线路中选择n-1条线路，以使总的线路最短？对于n个顶点的连通网可以建立许多不同的无向图，每一个无向图都可以表示一个道路网，其中要选择一个最优图，使图上各边之小。
这是我们课程设计的题目 开始我是用最小生成树去写的 不过后来发现好像这道题目是要用最短路径来做 现在问题是如果用最短路径做 那题目中说选一个医院，使其余的村庄到这所医院的距离总体来说较短，主要是总体这两个字 感觉好像是说要每个结点到其余结点的最短路径之和加起来，然后再比较大小，最小的就是医院 如果是这样 想请教一下这个算法要如何实现？？
[解决办法]
想了一下，该问题可以分解为两个问题
1. 对图中两两点计算最短路径
2. 寻找一顶点使其到各点的路径和最小
关键是第一步，是计算全局最短路径，用Floyd-Warshall算法，复杂度是O(N^3)
那么第二步即使简单地用遍历也才O(N^2)，不影响整体复杂度
[解决办法]
先算出，每个村庄之间的距离矩阵。
然后找出和最小的那一行，行号为所选医院。
第一步距离矩阵计算麻烦了点。
