有一个无向带权图，如下图,画的不是很标准。它是由4个相同的长方形组成的，长方形的长为5，高为3.共9个顶点（0，1，2，3，4，5，6，7，8），求每个顶点到其余8个顶点的距离之和
并找出这些和中值最小的一个点.也就是找出一个点，使其到其他各点的距离之和最短。
求高手指教啊 小弟感激不尽！！
0 _________1_________2
  |        |         |
3 |________|4________|5
  |        |         |
6 |________|7________|8

[[it] 本帖最后由 kgb2000 于 2008-4-11 16:09 编辑 [/it]]

首先你这图是不是数字标错了。
这个赋权无向图可以用邻接矩阵来做。

图没有错，画的不太好。那个数字是顶点，权就是每条边的边长。就是用一个迭代循环，但是具体怎么写 还请指教啊

晕了，不是说四个一样的矩形吗？那就是每边长5高3喽？你的图上的顶点怎么有数字重复的？怎么2没有，8有两个。。。

不好意思 该过来了
就是一个无向图 意思就是有9个点 求出一个点 使这个点到其余各点的总距离最短
原题是个应用题 求建一个商店，使其到其余8户的总路径最短  我把他简化了；

在问题规模较大的情况下请选择随机优化算法。
这个问题规模较小，可以用邻接矩阵表示图形。因为是无向图，所以矩阵是对称矩阵。
每一行或列代表一个点序号，每个点到自己的距离为无穷大，若点之间没有边，则距离也为无穷大，否则，矩阵元素为5或3。
用循环计算每个行元素到其它列元素的矩阵元素值，取较小值即可。

有道理 ！！非常感谢！