一、问题的定义
求解单元点的最短路径问题：给出有向图g和源点v，求出从v到g中其他顶点的最短路径
约束条件：图表g中不存在负权重的边
二、思想
重点是，析构者最朴素的思想是按照长度增加的顺序产生最短路径。 也就是说，在对所有可见点的路径长度进行排序后，选择最短路径，即从相应顶点到源点的最短路径。
Tips )可视点是指从源点按照宽度优先算法扫描顶点的过程中搜索到的点。
接下来，让我们来解释一下，从源到所有可见点的路径中，长度最短的路径一定是从源到该点的最短路径，通过几个当前不可见点间接到达该点的路径是否比它短。
设图表g的顶点的集合为v，另一个集合s表示求出最短路径终点的集合(s是如何来的将在后面说明)。
假设下一条最短路径(终点为x )，则只能通过弧) v，x )或s的顶点到达x，vi，x )。 让我证明一下：
假设) v，x )路径上有一个不在s中的顶点，则目标不在s中，并且路径长度比该路径短。 但这是不可能的。 我们按照长度增加的顺序生成各最短路径，所以生成长度比该路径短的所有路径，他们的终点一定在s。
三.算法
1 .初始化。 v是g的所有顶点的集合，S={v}。 D[x]表示从源到x的已知路径，初始D[v]为0，其馀为无限大。
2 .从源点v开始执行一步广度优先算法，查找其邻点。 从下图的源点0开始，找到的可视点为1、2、3。
3 .计算从可见点到源点v的路径长度并更新D[x]。 然后，对路径进行排序，为了确定找到的最短路径，选择最短的，将其终点加到s上，那里找到的点是2，所以把2加到s上。 S={v，2}
4 .从s中选择新添加的点，执行宽度优先算法，查找其相邻点，重复step3。 如果图中有不连续的点，直到所有点都被添加s或者找不到新的可见点，则结束SV )算法。
总结：
戴克斯特拉的算法一共做了两件事：
【1】不断运行宽度优先算法查找可视点，计算可视点到源点距离的长度
【2】从现在已知的路径中选择长度最短的路径，将其顶点添加到s中，作为确定发现的最短路径的顶点。
python的实现如下：
defDijkstra(graph，v0) : vnum=graph.numnodepaths={ } count=0cands=pqueue ) )， v0) ) vmin )表示从u到vmin已知的最小路径长度为plenwhilecountvnumandnotcands.empty ) : pLen，u， 在vmin=cands.get )下，提取从可见点到源点的最短路径之一，然后按优先级队列提取ifvmininpaths.keys (: continue paths [ vmin ]=(u，pLen ) wingraph.getoutEdges(vmin ) : #查找可见点if v not in paths.keys ) :cands.put((plenw，vmin，v ) ) count=1retthe
完整代码https://download.csdn.net/download/good Xin _ ie/11045007