单源最短路径——Dijkstra算法学习
浏览数：33 /
时间：2015年06月08日
每次都以为自己理解了Dijkstra这个算法，但是过没多久又忘记了，这应该是第4、5次重温这个算法了。
这次是看的胡鹏的《地理信息系统》，看完之后突然意识到用数学公式表示算法流程是如此的好理解，堪称完美。
内容摘抄如下：
网络中的最短路径是一条简单路径，即是一条不与自身相交的路径，最短路径搜索的依据：若从S点到T点有一条最短路径，则该路径上的任何点到S的距离都是最短的。
Dijkstra算法搜索步骤：
1.对起始点作标记S，且对所有顶点令D（X）=∞，Y=S；
2.对所有未做标记的点按以下公式计算距离
D（X）=min{D（X），d（Y，X）+D（Y）}，其中Y是最后一个做标识的点。
取具有最小值的D（X），并对XWT标记，令Y=X。
若最小值的D（X）=∞，则说明S到所有未标识的点都没有路，算法终止；否则继续。
3.如果Y=T，则已经找到了S到T的最短路径，算法终止。否则转到步骤2。
最短路径算法：Dijkstra算法和Floyd算法
图论
走一步：由起点StartNode A遍历一条边，选择最短的一条边链接到节点B，记距离dAB。
走两步：由B遍历相连的边，选择最短的一条边，记临时距离dtemp，此时距离dAB+dtemp；
和A走一步第二短距离比较，短的距离作为走两步的距离。
基本就是“一步一比，两步一回头”，保证得到这样的效果，每走一步都是最短路径。
参考：《插件式GIS应用框架的设计与实现：基于C#和AE 9.2》
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
