问题标题：
【用弗洛伊德算法求最短路径已知一有向网的邻接矩阵如下图所示,若需在其中一个结点建立娱乐中心,要求该结点距其他各结点的最长往返路程最短,相同条件下总的往返路程越短越好,问娱乐中】
问题描述：
用弗洛伊德算法求最短路径
已知一有向网的邻接矩阵如下图所示,若需在其中一个结点建立娱乐中心,要求该结点距其他各结点的最长往返路程最短,相同条件下总的往返路程越短越好,问娱乐中心应选址何处?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 53
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怎么求出来的?
陈绮回答：
是地信的题吧,先给你说v1怎么求,
先找出v1能去的最近的点,为V2,
如果S1i>S12+S2i
修改V1到Vi的距离为S12+S2i
然后去掉V2,在其余的点中找距V1最近的,按上面的方法修改
最后得到V1与其他各点的最短距离
同样的方法求出到其他点的最短距离
点击显示
数学推荐
热门数学推荐