用弗洛伊德算法求最短路径已知一有向网的邻接矩阵如下图所示,若需在其中一个结点建立娱乐中心,要求该结点距其他各结点的最长往返路程最短,相同条件下总的往返路程越短越好,问娱乐中
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/05 06:01:14
![用弗洛伊德算法求最短路径已知一有向网的邻接矩阵如下图所示,若需在其中一个结点建立娱乐中心,要求该结点距其他各结点的最长往返路程最短,相同条件下总的往返路程越短越好,问娱乐中](/uploads/image/z/8933269-13-9.jpg?t=%E7%94%A8%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%AE%97%E6%B3%95%E6%B1%82%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E5%B7%B2%E7%9F%A5%E4%B8%80%E6%9C%89%E5%90%91%E7%BD%91%E7%9A%84%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E5%A6%82%E4%B8%8B%E5%9B%BE%E6%89%80%E7%A4%BA%2C%E8%8B%A5%E9%9C%80%E5%9C%A8%E5%85%B6%E4%B8%AD%E4%B8%80%E4%B8%AA%E7%BB%93%E7%82%B9%E5%BB%BA%E7%AB%8B%E5%A8%B1%E4%B9%90%E4%B8%AD%E5%BF%83%2C%E8%A6%81%E6%B1%82%E8%AF%A5%E7%BB%93%E7%82%B9%E8%B7%9D%E5%85%B6%E4%BB%96%E5%90%84%E7%BB%93%E7%82%B9%E7%9A%84%E6%9C%80%E9%95%BF%E5%BE%80%E8%BF%94%E8%B7%AF%E7%A8%8B%E6%9C%80%E7%9F%AD%2C%E7%9B%B8%E5%90%8C%E6%9D%A1%E4%BB%B6%E4%B8%8B%E6%80%BB%E7%9A%84%E5%BE%80%E8%BF%94%E8%B7%AF%E7%A8%8B%E8%B6%8A%E7%9F%AD%E8%B6%8A%E5%A5%BD%2C%E9%97%AE%E5%A8%B1%E4%B9%90%E4%B8%AD)
用弗洛伊德算法求最短路径已知一有向网的邻接矩阵如下图所示,若需在其中一个结点建立娱乐中心,要求该结点距其他各结点的最长往返路程最短,相同条件下总的往返路程越短越好,问娱乐中
用弗洛伊德算法求最短路径
已知一有向网的邻接矩阵如下图所示,若需在其中一个结点建立娱乐中心,要求该结点距其他各结点的最长往返路程最短,相同条件下总的往返路程越短越好,问娱乐中心应选址何处?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与其他各点的最短距离
同样的方法求出到其他点的最短距离