探究最短路径问题：Dijkstra算法

上次写了关于数据结构的图。图的算法只有一个考点：最短路径问题。最短路径问题（ShortestPathProblems）：给定一个网络，在网络的边上有权重，找到一条从给定起点到给定终点的路径，使路径上的边权重之和最小。比如上图中：图中1点到4点的最短路径长度应该是3（从1到2再到4）。Dijkstra算法常用来解决最短路径问题Dijkstra算法Dijkstra算法是一种典型的单源最短路径算法，用于计算从一个节点到所有其他节点的最短路径。主要特点是起点为中心，逐层向外扩展，直至到达终点。比如上图中的Dijkstra算法就是不断的寻找起始节点到邻居节点的所有路径，设置初始距离为最短距离，然后不断更新邻居节点的最短距离，直到最短距离最远节点的解决。的过程。文字描述不清楚，看下面动图。图上的顶点分为两组已访问节点和未访问节点。每次从visited扩展一个点，扩展规则是可更新点之间的最小距离。我们以上图为例，先用邻接矩阵表示无向图：MAX=9999g=[[0,1,4,6],[MAX,0,MAX,2],[MAX,MAX,0,1],[MAX,MAX,MAX,0]]邻接矩阵g[0][1]=1表示第一个节点到第二个节点的距离为1。目的是求起点1到其他点的最小路径距离n=4#4个点#初始化visitedvisitd=[0]*(n)#记录该点是否被访问过#第一个点访问过visitd[0]=1#初始化源点到每个点节点的距离集合d=g[0]foriinrange(2,n):#遍历d取出权重最小的节点位置minWeigth=MAXforjinrange(2,n):ifd[j]d[k]+g[k][j]andvisitd[j]==0:d[j]=d[k]+g[k][j]foriinrange(1,n):print(d[i])145至此，节点1到其他三个节点的最短距离分别为1、4、5。”应用Dijkstra的算法到未加权的图，或所有边上权重相等的图。Dijkstra的算法等同于BFS搜索。”在很多情况下，多点求解需要输入一组点，然后找到一个起点的输入。获取无向图中的最短路径。importmath#假设图中的顶点数V=6#标记数组：used[v]的值为False，表示变化的顶点还没有被访问过，在S中，否则在U中！used=[Falsefor_inrange(V)]#距离数组：distance[i]表示源点s到i的最短距离，distance[s]=0distance=[float('inf')for_inrange(V)]#cost[u][v]表示边e=(u,v)的权重，如果不存在则设置为INF#cost接收表cost=[[float('inf')for_inrange(V)]for_inrange(V)]defdijkstra(s):distance[s]=0whileTrue:#v这里相当于一个哨兵，统一处理起点s！v=-1#选择一个与未使用的顶点距离最小的顶点foruinrange(V):ifnotused[u]and(v==-1ordistance[u]