参考答案：该图的邻接矩阵如下：

利用Floyd算法可求得两顶点之间最短路径长度。最后求得：

从A₄中可求得每对村庄之间的最少交通代价。假设医院建在i村庄时，其他各村庄往返总的交通代价如下所示：
医院建在村庄0时，各村庄往返总的交通代价为12+16+4+7+13+16+4+18=90；
医院建在村庄1时，各村庄往返总的交通代价为13+29+17+20+12+11+8+5=115；
医院建在村庄2时，各村庄往返总的交通代价为16+11+12+6+16+29+12+34=136；
医院建在村庄3时，各村庄往返总的交通代价为4+8+12+3+4+17+12+22=82；
医院建在村庄4时，各村庄往返总的交通代价为18+5+34+22+7+20+6+3=115。
显然，把医院建在村庄3时总体交通代价最少。

解析： 本题主要考查Floyd算法的思想和解题步骤。Floyd算法的基本思想是：假设求从顶点v_i到v_j的最短路径。如果从v_i到v_j有弧，则从v_i到v_j存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，尚需进行n次试探。
(1)首先考虑路径(v_i，v₀，v_j)是否存在，即判别弧(v_i，v₀)和(v₀，v_j)是否存在。如果存在，则比较(v_i，v_j)和(v_i，v₀，v_j)的路径长度，取长度较短者为从v_i到v_j的中间顶点的序号不大于0的最短路径。
(2)假如在路径上再增加一个顶点v₁，也就是说，如果(v_i，…，v₁)和(v₁，…，v_j)分别是当前找到的中间顶点的序号不大于0的最短路径，那么(v_i，…，v₁，…，v_j)就有可能是从v_i到v_j的中间顶点的序号不大于1的最短路径。将它和已经得到的从v_i到v_j中间顶点序号不大于0的最短路径相比较，从中选出中间顶点的序号不大于1的最短路径之后，再增加一个顶点v₂，继续进行试探。依次类推。
(3)在一般情况下，若(v_i，…，v_k)和(v_k，…，v_i)分别是从v_i到v_k和从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)按此方法，可以同时求得各对顶点间的最短路径。