用弗洛伊德算法求最短路径

Question

已知一有向网的邻接矩阵如下图所示，若需在其中一个结点建立娱乐中心，要求该结点距其他各结点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处？v1   0   2  ∞  ∞  ∞  3
  v2  ∞  0    3  2   ∞  ∞
 v3   4  ∞   0  ∞  4   ∞
 v4   1  ∞  ∞   0  1   ∞
 v5  ∞  1   ∞  ∞  0    3
   v6  ∞  ∞   2   5  ∞   0    
解题过程：v1   0   2  5  4  5 3
  v2  3  0   3  2   3  6
 v3   4  5   0  7  4   7
 v4   1  2  5   0  1   4
 v5  4  1   4  3  0   3
   v6  6  7   2   5  6   0  
设Vj到各顶点的往返距离和为S（Vj）
到其他各顶点的最长往返路程为L（Vj），则
L（V1）＝9，S（V1）＝37
L（V2）＝13，S（V2）＝34
L（V3）＝12，S（V3）＝46
L（V4）＝12，S（V4）＝34
L（V5）＝9，S（V5）＝34
L（V6）＝13，S（V6）＝49

我会画出图，但是L和S怎么求出来的？

Answer 1

是地信的题吧，先给你说v1怎么求，
先找出v1能去的最近的点，为V2，
如果S1i>S12+S2i
修改V1到Vi的距离为S12+S2i
然后去掉V2，在其余的点中找距V1最近的，按上面的方法修改
最后得到V1与其他各点的最短距离
同样的方法求出到其他点的最短距离