迪杰斯特拉算法总结.doc

《迪杰斯特拉算法总结.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、总结：最短路径算法关键先把已知最短路径顶点集(只有一个源点)和未知的顶点分开，然后依次把未知集合的顶点按照最短路径(这里特别强调一下是源点到该顶点的路径权重和，不仅仅是指它和父结点之间的权重，一开始就是在没有这个问题弄清楚)加入到已知结点集中。在加入时可以记录每个顶点的最短路径，也可以在加入完毕后回溯找到每个顶点的最短路径和权重。迪杰斯特拉算法用于求解一个有向图（也可以是无向图，无向图是有向图的一种特例）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。算法构思很是巧妙（我这么认为），简直达到了“无心插柳柳成荫”的境界。算法本身并不

2、是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列（如果这个有向图中有环1-2-3-1算法岂不是永无终结之日了？？！！），但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。算法把一个图（G）中的点划分成了若干部分：1）：原点（v）；2）：所有周边点（C）；另外有一个辅助集合S，从v到S中的点的

3、最短路径已经求得。S的最初状态是空集。这样就可以进一步划分图（G）：1）：原点（v）；2）：已求出v至其最短路径的周边点（S）；3）：尚未求出v至其最短路径的周边点（Other=C-S）；算法的主体思想：A、找到v——Other所有路径中的的最短路径vd=v——d（Other的一个元素）；B、找到v——S——Other所有路径中的的最短路径vi=v——i（Other的一个元素）；C、比较vd和vi如果vd<=vi则将d加入S且从Other中删除，否则将i加入S且从Other中删除。重复以上步骤直至Other为空集。我们求得的最短路径是升序排列的，

4、那为什么下一条最短路径就存在于v——用到了贪心的策略找最短的未拓展节点，加入已拓展部分然后再根据此节点，重新更新未拓展部分就是通过一个方法，找到起始位置到目标位置的最优化路线Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。　　Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。　　Dijkstra一般的表述通

5、常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表方式，Drew为了和下面要介绍的A*算法和D*算法表述一致，这里均采用OPEN,CLOSE表的方式。　　其采用的是贪心法的算法策略　　大概过程：　　创建两个表，OPEN,CLOSE。　　OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。　　1．访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。　　2．从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。　　3．遍历考察这个点的子节点。求出这

6、些子节点距起始点的距离值，放子节点到OPEN表中。　　4．重复第2和第3步,直到OPEN表为空，或找到目标点。