##python算法之Dijkstra
Dijkstra算法是由荷兰计算机科学家迪杰斯特拉（Dijkstra）于1959 年提出的，因此又叫迪杰斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。
实现原理：
**每次新扩展一个距离最短的点，更新与其相邻的点的距离。**当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。
算法思路：
Dijkstra最短路经算法是一种单源最短路径，针对的是非负权边。所谓单源最短路径就是指定一个出发顶点，计算从该源顶点出发到其他所有顶点的最短路径。
按路径长度递增次序产生算法：
把顶点集合V分成两组：
（1）S：已求出的顶点的集合（初始时只含有源点V0）
（2）V-S=T：尚未确定的顶点集合
将T中顶点按递增的次序加入到S中，
保证：
（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度
（2）每个顶点对应一个距离值
S中顶点：从V0到此顶点的长度
T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度
依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和
代码实现：
import networkx as nxdef Dijkstra(G, start, end):RG = G.reverse();dist = {};previous = {}for v in RG.nodes():#都设置为无穷大dist[v] = float('inf')previous[v] = 'none'dist[end] = 0u = endprint(dist)print(min(dist, key=dist.get))while u != start:#获得最小值对应的键u = min(dist, key=dist.get)distu = dist[u]# print(distu)del dist[u]print(RG.edges(u))print(RG[u])for u, v in RG.edges(u):if v in dist:alt = distu + RG[u][v]['weight']if alt < dist[v]:dist[v] = altprevious[v] = upath = (start,)last = startwhile last != end:nxt = previous[last]path += (nxt,)last = nxtreturn path#实例化一个空的图G = nx.DiGraph()#添加边G.add_edge(0, 1, weight=80)G.add_edge(1, 2, weight=50)G.add_edge(1, 3, weight=30)G.add_edge(3, 2, weight=10)G.add_edge(2, 4, weight=20)G.add_edge(2, 5, weight=30)G.add_edge(4, 5, weight=10)G.add_edge(5, 3, weight=5)G.add_edge(2, 6, weight=10)G.add_edge(4, 6, weight=10)G.add_edge(3, 6, weight=25)G.add_edge(5, 6, weight=35)rs = Dijkstra(G, 0, 6)print(rs)
运行结果：
(0, 1, 3, 2, 6)
想获取百本python书籍以及各种学习资料，请关注微信公众号：测试开发晋级之路，回复：学习书籍
