作业帮用弗洛伊德算法求最短路径已知一有向网的邻接矩阵如下图所示,若需在其中一个结点建立娱乐中心,要求该结点距其他各结点的最长往返路程最短,相同条件下总的往返路程越短越好,问娱乐中
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/03 18:00:23
用弗洛伊德算法求最短路径已知一有向网的邻接矩阵如下图所示,若需在其中一个结点建立娱乐中心,要求该结点距其他各结点的最长往返路程最短,相同条件下总的往返路程越短越好,问娱乐中
用弗洛伊德算法求最短路径
已知一有向网的邻接矩阵如下图所示,若需在其中一个结点建立娱乐中心,要求该结点距其他各结点的最长往返路程最短,相同条件下总的往返路程越短越好,问娱乐中心应选址何处?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怎么求出来的?
用弗洛伊德算法求最短路径已知一有向网的邻接矩阵如下图所示,若需在其中一个结点建立娱乐中心,要求该结点距其他各结点的最长往返路程最短,相同条件下总的往返路程越短越好,问娱乐中
是地信的题吧,先给你说v1怎么求,
先找出v1能去的最近的点,为V2,
如果S1i>S12+S2i
修改V1到Vi的距离为S12+S2i
然后去掉V2,在其余的点中找距V1最近的,按上面的方法修改
最后得到V1与其他各点的最短距离
同样的方法求出到其他点的最短距离