最短路径算法—dijkstra总结.docx

精品文档
精品文档
1
精品文档
Dijkstra 算法解释
本文引用三篇文章：分别是 谢光新 -Dijkstra算法，
zx770424 -Dijkstra算法，
中华子女英雄 -Dijkstra算法
精品文档
精品文档
1
精品文档
Dijkstra 算法解释
本文引用三篇文章：分别是 谢光新 -Dijkstra算法，
zx770424 -Dijkstra算法，
中华子女英雄 -Dijkstra算法
有兴趣的朋友请引用原文，由于分类很不相同难以查找，此处仅作汇总。
谢光新的文章浅易易懂，无需深入的数学功力，每一步都有图示，很适合初学者认识。
zx770424将每一步过程，都用图示方式和公式代码 伪代码对应也有助于， 代码
的理解。
中华子女英雄从大面上总结了Dijkstra的思想，并将演路图描叙出来了。起到总结的效果。
希望这篇汇总有助于大家对 Dijkstra算法的理解。
Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以开端点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点好多，所以效率低。
简介
Dijkstra(迪杰斯特拉 )算法是典型的单源 最短路径算法，用于计算一个节点到其他所有节点的
精品文档
精品文档
2
精品文档
最短路径。主要特点是以开端点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra

算法是很有
精品文档
精品文档
13
精品文档
代表性的最短路径算法，在好多专业课程中都作为基本内容有详尽的介绍，如

数据构造，图论，
精品文档
精品文档
13
精品文档
运筹学等等。

Dijkstra

一般的表述往常有两种方式，一种用永远和临时标号方式，一种是用

OPEN,
精品文档
精品文档
13
精品文档
CLOSE表的方式，这里均采用永远和临时标号的方式。注意该算法要求图中不存在负权边。
精品文档
精品文档
13
精品文档
算法描绘
精品文档
精品文档
13
精品文档
(这里描绘的是从节点

1开始到各点的

dijkstra

算法，其中

Wa->b

表示

a->b

的边的权值，

d(i)
精品文档
精品文档
13
精品文档
即为最短路径值

)
精品文档
精品文档
13
精品文档
1． 置会合

S={2,3,...n},数组

d(1)=0,d(i)=W1->i(1,i

之间存在边

)or+无穷大之间不存在边

)
精品文档
精品文档
13
精品文档
2． 在

S中，令

d(j)=min{d(i),i

属于

S}，令

S=S-{j}，若

S为空集则算法结束，否则转

3
精品文档
精品文档
13
精品文档
3． 对全部

i属于

S,如果存在边

j->i，那么置

d(i)=min{d(i),d(j)+Wj->i}

，转

2
精品文档
精品文档
13
精品文档
Dijkstra

算法思想为：设

G=(V,E)是一个带权有向图，把图中极点会合

V分红两组，第一组为
精品文档
精品文档
13
精品文档
已求出最短路径的极点会合 （用S表示，初始时 S中只有一个源点， 此后每求得一条最短路径 ,就
将 加入到会合 S中，直到全部极点都加入到 S中，算法就结束了），第二组为其余未确定最短路
径的极点会合（用 U表示），按最短路径长度的递增序次依次把第二组的极点加入 S中。在加入
的过程中，总保持从源点 v到S中各极点的最短路径长度不大于从源点 v到U中任何极点的最短
路径长度。别的，每个极点对应一个距离， S中的极点的距离就是从 v到此极点的最短路径长度，
U中的极点的距离，是从 v到此极点只包括 S中的极点为中间极点的目前最短路径长度。
算法详细步骤
（1）初始时， S只包含源点，即 S=，v的距离为 0。U包含除 v外的其他极点， U中极点 u
距离为边上的权（若 v与u有边）或 ）（若 u不是v的出边毗邻点）。
（2）从U中选用一个距离 v最小的极点 k，把k，加入 S中（该选定