[图]最短路径-Dijkstra算法
- 2020 年 3 月 13 日
- 筆記
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 -来自百度百科
一.最短路径问题的求解
1、单源最短路径用Dijkstra算法；
2、所有顶点间的最短路径用Floyd算法。
二.Dijkstra算法
开始之前我们需要知道的一些知识点：
1.Dijkstra算法只能用于边权为正的图中，时间复杂度为O(n^2)；
2.BFS可能会是Dijkstra算法的实质，BFS使用的是队列进行操作，而Dijkstra采用的是优先队列。
Dijikstra算法所求解的问题是：大概有这样一个有权图，Dijkstra算法可以计算任意节点到其他节点的最短路径。
案例图
1.算法思路
1.指定一个节点，例如我们要计算 'A' 到其他节点的最短路径；
2.引入两个集合（S、U），S集合包含已求出的最短路径的点（以及相应的最短长度），U集合包含未求出最短路径的点（以及A到该点的路径，注意 如上图所示，A->C由于没有直接相连 初始时为∞）；
3.初始化两个集合，S集合初始时 只有当前要计算的节点，A->A = 0；
4.U集合初始时为 A->B = 4, A->C = ∞, A->D = 2, A->E = ∞；
5.从U集合中找出路径最短的点，加入S集合，例如 A->D = 2；
6.更新U集合路径，if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 则更新U；
7.循环执行 4、5 两步骤，直至遍历结束，得到A 到其他节点的最短路径。
2.算法图解
1.选定A节点并初始化，如上述步骤3所示；
图解1
2.执行上述 4、5两步骤，找出U集合中路径最短的节点D 加入S集合，并根据条件 if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 来更新U集合；
图解2
3.这时候 A->B, A->C 都为3，没关系。其实这时候他俩都是最短距离，如果从算法逻辑来讲的话，会先取到B点。而这个时候 if 条件变成了 if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' ) ，如图所示这时候A->B距离 其实为 A->D->B；
图解3
4.思路就是这样，往后就是大同小异了；
图解4
5.算法结束。
图解5
采用表格表示为：
<a href="https://study.sqdxwz.com/usr/uploads/2019/10/3387651027.jpg" class="highslide" onclick="return hs.expand(this,{slideshowGroup:'images'})"><img src="https://study.sqdxwz.com/usr/uploads/2019/10/3387651027.jpg" height="330" width="495"></a>
3.代码实现（python）
# dijkstra算法实现，有向图和路由的源点作为函数的输入，最短路径最为输出 def dijkstra(graph,src): # 判断图是否为空，如果为空直接退出 if graph is None: return None nodes = [i for i in range(len(graph))] # 获取图中所有节点 visited=[] # 表示已经路由到最短路径的节点集合 if src in nodes: visited.append(src) nodes.remove(src) else: return None distance={src:0} # 记录源节点到各个节点的距离 for i in nodes: distance[i]=graph[src][i] # 初始化 # print(distance) path={src:{src:[]}} # 记录源节点到每个节点的路径 k=pre=src while nodes: mid_distance=float('inf') for v in visited: for d in nodes: new_distance = graph[src][v]+graph[v][d] if new_distance < mid_distance: mid_distance=new_distance graph[src][d]=new_distance # 进行距离更新 k=d pre=v distance[k]=mid_distance # 最短路径 path[src][k]=[i for i in path[src][pre]] path[src][k].append(k) # 更新两个节点集合 visited.append(k) nodes.remove(k) print(visited,nodes) # 输出节点的添加过程 return distance,path if __name__ == '__main__': graph_list = [ [0, 2, 1, 4, 5, 1], [1, 0, 4, 2, 3, 4], [2, 1, 0, 1, 2, 4], [3, 5, 2, 0, 3, 3], [2, 4, 3, 4, 0, 1], [3, 4, 7, 3, 1, 0]] distance,path= dijkstra(graph_list, 0) # 查找从源点0开始带其他节点的最短路径 print(distance,path)
