数学建模社区-数学中国»论坛 › 【数模论坛】国家竞赛 › 数学中国数学建模网络挑战赛(TZMCM) › 最短路径算法

查看: 2148|回复: 1

最短路径算法

[复制链接]

字体大小: 正常放大

steve_wang

12 主题	5 听众	233 积分

TA的每日心情

	开心 2015-9-15 21:48

签到天数: 66 天

[LV.6]常住居民II

自我介绍: 数学爱好者

电梯直达

1^#

发表于 2013-7-10 17:19 手机频道 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

有没有大神懂必须经过某些指定点的dijkstra算法，最好能给个程序，谢谢！

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

袁海亮

148 主题	160 听众	2万积分

TA的每日心情

	难过 2021-12-27 17:15

签到天数: 337 天

[LV.8]以坛为家I

2013挑战赛参赛者

群组: 2013年第二期美赛论文

群组: 2013年国赛赛前培训

群组: 网络挑战赛一阶段C题

群组: 2013年数学建模国赛备

群组: 有事没事来点事做

2^#

发表于 2013-7-10 18:39 |只看该作者 |招呼Ta 关注Ta

Dijkstra算法
解单源最短路径问题的贪心算法。基本思想是设置顶点集合S并不断作贪心选择扩充这个集合。
一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。
Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。

QQ截图20130710183752.jpg (82.64 KB, 下载次数: 381)