如下图,找出C1到C6的一条最短路径并求出其路程总长度.如下图,找出C1——C6的最短路径并求出其路程总长补充格式如下:A-B 两点间距离c1-c2 4c1-c3 8c2-c3 3c2-c4 4c2-c5 6c3-c4 2c3-c5 2c4-c5 4c4-c6 9c5-c6 4
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/23 17:16:13
如下图,找出C1到C6的一条最短路径并求出其路程总长度.如下图,找出C1——C6的最短路径并求出其路程总长补充格式如下:A-B 两点间距离c1-c2 4c1-c3 8c2-c3 3c2-c4 4c2-c5 6c3-c4 2c3-c5 2c4-c5 4c4-c6 9c5-c6 4
如下图,找出C1到C6的一条最短路径并求出其路程总长度.如下图,找出C1——C6的最短路径并求出其路程总长
补充格式如下:A-B 两点间距离
c1-c2 4
c1-c3 8
c2-c3 3
c2-c4 4
c2-c5 6
c3-c4 2
c3-c5 2
c4-c5 4
c4-c6 9
c5-c6 4
如下图,找出C1到C6的一条最短路径并求出其路程总长度.如下图,找出C1——C6的最短路径并求出其路程总长补充格式如下:A-B 两点间距离c1-c2 4c1-c3 8c2-c3 3c2-c4 4c2-c5 6c3-c4 2c3-c5 2c4-c5 4c4-c6 9c5-c6 4
我来试试吧...
这个问题其实就是图论中的 最短路径 算法...方法很多...
我用个最直接的吧 最小树原理...Johnson算法
首先,我们可以发现有这样一个事实:如果P是G中从vs到vj的最短路,vi是P中的一个点,那么,从vs沿P到vi的路是从vs到vi的最短路.
于是,在多通道时,选择权重(这里就是距离)较小的路径;当权重平衡,任选其一
实际上就是保证,从vs,vs+1,vs+2 构成的三角形中,选择其一边时,为最短边;选择其两边时,两边的权和(这里是长度和)小于第三边即可.
按照上述方法通过的无圈图为最小生成树
d(C1-C2)=4
d(C1-C3)=8 选择 C1-C2
d(C2-C3)=3,
d(C2-C4)=4
d(C2-C5)=6,选择 C2-C3
d(C3-C4)=2
d(C3-C5)=2,选择C3-C4,C3-C5都可以,但发现d(C4-C6)=9>d(C5-C6)=4
选择C3-C5
最后C5-C6
我们得到了最小生成树 C1-C2-C3-C5-C6 总长度为 13
我们验证下它是最小的:C1C2C3三角形,我们选择了两边,C1C2+C2C3
如下图,找出C1到C6的一条最短路径并求出其路程总长度。 如下图,找出C1——C6的最短路径并求出其路程总长
没有图,楼上怎么做的?服了.。是图论的问题没错