Dijkstra算法（迪科斯彻算法、迪杰斯特拉算法）：
迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
提出者：
艾兹格·W·迪科斯彻 （Edsger Wybe Dijkstra，1930年5月11日~2002年8月6日）荷兰人。 计算机科学家，毕业就职于荷兰Leiden大学，早年钻研物理及数学，而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖，之后，他还获得过1974年 AFIPS Harry Goode Memorial Award、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACM PODC最具影响力论文奖。
Dijkstra算法python实现：
import heapq
import sysclass Graph:def __init__(self):self.vertices = {}def add_vertex(self, name, edges):self.vertices[name] = edgesdef get_shortest_path(self, startpoint, endpoint):#distances使用字典的方式保存每一个顶点到startpoint点的距离distances = {}#从startpoint到某点的最优路径的前一个结点#eg:startpoint->B->D->E,则previous[E]=D,previous[D]=B,等等previous = {}#用来保存图中所有顶点的到startpoint点的距离的优先队列#这个距离不一定是最短距离nodes = []#Dikstra算法 数据初始化for vertex in self.vertices:if vertex == startpoint:#将startpoint点的距离初始化为0distances[vertex] = 0heapq.heappush(nodes, [0, vertex])elif vertex in self.vertices[startpoint]:#把与startpoint点相连的结点距离startpoint点的距离初始化为对应的弧长/路权distances[vertex] = self.vertices[startpoint][vertex]heapq.heappush(nodes, [self.vertices[startpoint][vertex], vertex])previous[vertex] = startpointelse:#把与startpoint点不直接连接的结点距离startpoint的距离初始化为sys.maxsizedistances[vertex] = sys.maxsizeheapq.heappush(nodes, [sys.maxsize, vertex])previous[vertex] = Nonewhile nodes:#取出队列中最小距离的结点smallest = heapq.heappop(nodes)[1]if smallest == endpoint:shortest_path = []lenPath = distances[smallest]temp = smallestwhile temp != startpoint:shortest_path.append(temp)temp = previous[temp]#将startpoint点也加入到shortest_path中shortest_path.append(temp)if distances[smallest] == sys.maxsize:#所有点不可达break#遍历与smallest相连的结点，更新其与结点的距离、前继节点for neighbor in self.vertices[smallest]:dis = distances[smallest] + self.vertices[smallest][neighbor]if dis < distances[neighbor]:distances[neighbor] = dis#更新与smallest相连的结点的前继节点previous[neighbor] = smallestfor node in nodes:if node[1] == neighbor:#更新与smallest相连的结点到startpoint的距离node[0] = disbreakheapq.heapify(nodes)return shortest_path, lenPath
if __name__ == '__main__':g = Graph()g.add_vertex('a', {'b':6, 'd':2, 'f':5})g.add_vertex('b', {'a':6, 'c':4, 'd':5})g.add_vertex('c', {'b':4, 'e':4, 'h':6})g.add_vertex('d', {'a':2, 'b':5, 'e':6, 'f':4})g.add_vertex('e', {'d':6, 'c':4, 'g':5, 'h':4})g.add_vertex('f', {'a':5, 'd':4, 'g':9})g.add_vertex('g', {'f':9, 'e':5, 'h':5})g.add_vertex('h', {'c':6, 'e':4, 'g':5})start = 'a'end = 'e'shortestPath, len = g.get_shortest_path(start, end)print('{}->{}的最短路径是：{}，最短路径为：{}'.format(start, end, shortestPath, len))最后的测试用例使用的是无向图：
代码如有误，欢迎评论指出
