[图]最短路径-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)