下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?
【正确答案】正确答案：该图的邻接矩阵如下：
利用F1oyd算法可求得两顶点之间最短路径长度。最后求得：
利用F1oyd算法可求得两顶点之间最短路径长度。最后求得：
【答案解析】解析：本题主要考查Floyd算法的思想和解题步骤。Floyd算法的基本思想是： 假设求从顶点v
i
到v
j
的最短路径。如果从v
i
到v
j
，有弧，则从v
i
到v
j
存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，尚需进行n次试探。 (1)首先考虑路径(v
i
，v
0
，v
j
)是否存在，即判别弧(v
i
，v
0
)和(v
0
，v
j
)是否存在。如果存在，则比较(v
i
，v
j
)和(v
i
，v
0
，v
j
，)的路径长度，取长度较短者为从v
i
到v
2j
，的中间顶点的序号不大于O的最短路径。 (2)假如在路径上再增加一个顶点v
1
，也就是说，如果(v
i
，……，v
1
)和(v
1
，……，v
j
)分别是当前找到的中间顶点的序号不大于0的最短路径，那么(v
i
，……，v
1
。，……，v
j
)就有可能是从v
i
到
j
的中间顶点的序号不大于1的最短路径。将它和已经得到的从v
i
到v
j
，中间顶点序号不大于O的最短路径相比较，从中选出中间顶点的序号不大于1的最短路径之后，再增加一个顶点v
2
，继续进行试探。依次类推。 (3)在一般情况下，若(v
i
，……，v
k
)和(v
k
，……，v
j
)分别是从v
k
到v
j
和从口。到口，的中间顶点的序号不大于k－1的最短路径，则将(v
i
，……，v
k
，……，v
j
)和已经得到的从v
i
到v
j
且中间顶点序号不大于k－1的最短路径相比较，其长度较短者便是从v
i
到v
j
，的中间顶点的序号不大于k的最短路径。这样，在经过n次比较后，最后求得的必是从v
i
到v
j
的最短路径。 (4)按此方法，可以同时求得各对顶点间的最短路径。