Dijkstra )算法是典型的单源最短路径算法，该算法我自主学习了三次。 第一次自主学习的时候，我在看fdwl的《数据结构》。 当时应该理解，稍微完全理解了这个算法，但是没有记录。 后来就忘了。 在第二次自主学习中，我在网上找了相关文章，读了很多关于这个算法的说明，我很了解。 昨天晚上突然又想到了这个算法，我发现我还不熟悉这个算法，又忘记了Dijkstra算法是怎么回事，决定再看一遍这个算法。 已经12点了，平时这个时候已经躺在床上了。 这次终于彻底理解了，决定做成博客记录下来。
Dijkstra算法用于搜索权利地图，并查找地图中两点的最短距离。 既不是DFS搜索，也不是BFS搜索。
如果将Dijkstra算法应用于无权限图或所有边权相等的图，则Dijkstra算法等同于BFS搜索。
3358 www.cn blogs.com/biyeymyhjob/archive/2012/07/31/2615833.html
2 .算法说明
1 )算法思想) g=) v， 将e )作为有向图，将图表中的顶点集合v分为两组，第一组是已经求出了最短路径的顶点集合(用s表示，在初始时刻s只有一个源点，以后每次求出最短路径时都被追加到集合s中，直到所有的顶点都被追加到s中为止，这是算法在添加第二组是剩下的未定最短路径的过程中，从源点到s的每个顶点的最短路径的长度将保持不大于从源点到u的任何顶点的最短路径的长度。 另外，各顶点与一个距离相对应，s中顶点的距离为从v到此顶点的最短路径长度，u中顶点的距离为从v到此顶点只将s中顶点作为中间顶点的当前最短路径长度。
范例
不要看算法的视频，在理解算法的时候，思考比不上GIF视频的速度，这两幅图最有助于理解算法
需要重点理解这个拗音的'按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度'
实际上，Dijkstra 算法是一个排序过程，以上面的例子来说，是根据从a到图中剩下的点的最短路径的长度来排序的，路径越短越先被发现，路径越长越晚被发现。 要寻找从a到f的最短路径，按顺序找到了
A -- C的最短路径3
A----C----B的最短路线5
A----C----D的最短路线6
A----C----E的最短路线7
a---c---d---f的最短路线9
Dijkstra算法执行的附加效果是从a到c的路径最短，其次可以得到从a到b、从a到d、从a到e、从a到f的其他信息
为什么Dijkstra算法不适用于拥有负权利的图？
以前面的例子来说，将某一点选择为集合s时，就意味着找到了从a到此点的最短路径。 例如，在步骤2中，将c点选为集合s时，意味着找到了从a到c的最短路径。 但是，如果图中有负权重的边，就不能再多说了。 例如，假设有一个点z。 z只与a和c相连。 从a到z的权重为50，从z到c的权重为-49。 现在从a到c的最短路径明显是A -- Z -- C
拥有负权利的图应该使用Floyd算法
再举一例， 初点a到b最短有权10，b到c有权50，a到d有权30，d到c有权20，求a到c的最短路径。
戴克斯特拉算法的执行过程是一个排序的过程，既不是深度优先，也不是广度优先。 在这个简单示例中，A和B都加入了s集合，然后再加入s集合节点未必是C节点。 请将由a和b节点构成的集合作为一体来考虑。 算法运行到a和b都加入到s集合中后，甚至可以从图上去除a和b，用虚拟的s节点表示。 A和B成为一体后，与这个整体相连的边，最短的是A到D这一边。 但是，此时，不能因为这一带的权重最小就直接把d加到s集合上。 现在，假设B到C的权利是25而不是50。 目前，与s集合相连的边是a到d 30，b到c 25； 此时，b到c的权重最小，但不能加入s集合。 从a到b再到c的权重是10 25，已经大于从a到d的权重30，所以d应该加入s集合而不是c； 如果b到c的权重小于20，则c将先参加s集合而不是d，b到c的权重正好为20，无论是先把d放入s还是先把c放入s都一样。 没有区别。
另外，任意一点k在加入s集合后，找到了从原点a到k的最短路径，其前提条件是图中没有带负数的加权边。 这样表达可以让算法更清晰。 还是这个例子？ a和b都被选为s集合后，去更新整个图。 去掉a和b两者，用新的节点s代替a和b。 s到d有30的权利，s到c有10到50的权利。 接下来应该选择哪个节点并入s集合一目了然吧。 d点被选为s集合后，从图上删除d点，更新从虚拟节点s到c的权重