迪杰斯特拉算法总结(共4页)

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

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

3、 1）：原点（v）； 2）：已求出v至其最短路径的周边点（S）； 3）：尚未求出v至其最短路径的周边点（Other=C-S）； 算法的主体思想： A、找到vOther所有路径中的的最短路径vd=vd（Other的一个元素）； B、找到vSOther所有路径中的的最短路径vi=vi（Other的一个元素）； C、比较vd和vi如果vd<=vi则将d加入S且从Other中删除，否则将i加入S且从Other中删除。 重复以上步骤直至Other为空集。 我们求得的最短路径是升序排列的，那为什么下一条最短路径就存在于v用到了贪心的策略 找最短的未拓展节点，加入已拓展部分 然后再根据此节点，重新更新

4、未拓展部分 就是通过一个方法，找到起始位置到目标位置的最优化路线Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。其采用的是贪心法的算法策略大概过程：创建两个表，OPEN, CLOSE。OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。1 访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。2 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。3 遍历考察