带权重的最优路径解法

jerryxjr1220 · 发表于 2017-1-5 09:02:18

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 jerryxjr1220 于 2017-1-5 09:06 编辑

带权重的最优路径解法是现在用的许多导航地图算法的基础，所以还是很有必要研究一下的。

例如：
题目要求：起点（0），终点（9），找出权重最小的路径即为最优路径

weight={0:{1:3,2:5,3:6,4:8,5:4,6:9,7:8,8:9,9:16,10:3,11:2},
        1:{0:2,2:3,3:3,4:4,5:3,6:7,7:2,8:8,9:12,10:4,11:5},
        2:{0:2,1:5,3:4,4:9,5:3,6:6,7:2,8:5,9:10,10:3,11:3},
        3:{0:5,1:2,2:6,4:6,5:5,6:3,7:6,8:7,9:10,10:4,11:4},
        4:{0:7,1:9,2:2,3:7,5:3,6:8,7:3,8:2,9:10,10:5,11:4},
        5:{0:4,1:3,2:3,3:2,4:2,6:8,7:4,8:5,9:11,10:4,11:5},
        6:{0:2,1:2,2:3,3:3,4:4,5:5,7:6,8:5,9:6,10:4,11:5},
        7:{0:3,1:3,2:2,3:4,4:3,5:4,6:3,8:2,9:9,10:4,11:5},
        8:{0:2,1:2,2:4,3:1,4:2,5:3,6:1,7:3,9:6,10:4,11:5},
        9:{0:1,1:3,2:5,3:7,4:2,5:4,6:6,7:3,8:8,10:4,11:5},
        10:{0:1,1:3,2:5,3:7,4:2,5:4,6:6,7:3,8:8,9:12,11:5},
        11:{0:1,1:2,2:5,3:7,4:2,5:4,6:6,7:3,8:8,9:12,10:4}}

源代码：

游客，如果您要查看本帖隐藏内容请回复

输出：
[12, [0, 11, 11, 4, 4, 8, 8, 9]]
[Finished in 0.1s]

增加了“途经”功能，可以最多设置2个途径点，比如7和3，输出：
[17, [0, 1, 1, 7, 7, 8, 8, 3, 3, 6, 6, 9]]
[Finished in 0.1s]

逝痕 · 发表于 2017-1-5 12:31:51

Python死忠粉 · 发表于 2017-8-13 19:22:41

查看源代码

摩羯马拉松 · 发表于 2017-9-25 10:32:50

code

khd · 发表于 2017-11-24 09:33:39

学习

996561465 · 发表于 2018-3-29 08:32:05

倪小孙 · 发表于 2018-6-14 15:18:56

hao

qaz123765 · 发表于 2019-7-16 09:11:03

看看

账号		自动登录	找回密码
密码			立即注册

[技术交流] 带权重的最优路径解法

马上注册，结交更多好友，享用更多功能^_^