网页网站建设难吗,如何做网站源码,网页设计与制作概述,上海建筑建材业信息网什么是Dijkstra算法#xff1f; Shortest Path Tree (SPT) 单源最短路径算法 从指定节点出发#xff0c;到达任何其他节点的距离最短。
和K算法、P算法的区别是#xff1f; K算法、P算法#xff0c;这两个算法都是最小生成树算法 Minimal Spanning Tree#xff08;MST Shortest Path Tree (SPT) 单源最短路径算法 从指定节点出发到达任何其他节点的距离最短。
和K算法、P算法的区别是 K算法、P算法这两个算法都是最小生成树算法 Minimal Spanning TreeMST保证整个拓扑图的所有路径之和最小。
class Dijkstra:Shortest Path Tree (SPT) 单源最短路径算法从指定节点出发到达任何其他节点的距离最短def __init__(self):passdef weight(self, start, end):# 返回节点start到end的权重passdef adj(self, s):# 返回节点s的所有相邻节点passdef dijkstra(self, s, graph: List[List[int]]) - List[int]:输入一张图和一个起点计算该点到其他节点的最短路径:param start::param graph::return:v len(graph)# dp tabledistTo[i]可理解为节点s到节点i的最短路劲后续要不停地更新该表distTo [float(inf)] * v# base casedistTo[s] 0min_heap []# 从起点s开始BFSheapq.heappush(min_heap, self.State(s, 0))while min_heap:curState heapq.heappop(min_heap)curNodeID curState.idcurDistFromStart curState.distFromStart# 如果只关心start 节点到某一个终点end的最短距离此处加入一个判断即可# if curNodeID end:# return curDistFromStartif curDistFromStart distTo[curNodeID]:# 已经有一条更短的路径到达curNode节点了continue# 遍历curNodeID的相邻节点for nextNodeID in self.adj(curNodeID):distToNextNode curDistFromStart self.weight(curNodeID, nextNodeID)if distToNextNode distTo[nextNodeID]:# 更新dp tabledistTo[nextNodeID] distToNextNode# 将该邻居节点加入优先级队列heapq.heappush(min_heap, self.State(nextNodeID, distToNextNode))class State:def __init__(self, id, distFromStart):从start节点到当前节点的距离:param id::param distFromStart:self.id idself.distFromStart distFromStartdef __lt__(self, other):if self.distFromStart other.distFromStart:return Truereturn False
