深圳网站-建设信科网络,网站建设与管理实训,个人简历表模板电子版,淄博 网站运营dijsktra算法模板#xff1a;
def dijkstra(x):#x表示出发点dis[inf]*n #dis记录从x出发到各个点的最短距离#xff0c;初始化为infdis[x]0 #源点到自己的距离为0vis[False]*n #检查各个点是否访问过for _ in range(n-1): #检查除了源点的其他n-1个点#xff0c;更新dis…dijsktra算法模板
def dijkstra(x):#x表示出发点dis[inf]*n #dis记录从x出发到各个点的最短距离初始化为infdis[x]0 #源点到自己的距离为0vis[False]*n #检查各个点是否访问过for _ in range(n-1): #检查除了源点的其他n-1个点更新disnode-1 #开始假设不知道谁是离源点最近的点for j in range(n):#循环查找谁是离源点最近的那个点if not vis[j] and (node-1 or dis[j]dis[node]):nodejfor j in range(n):#对node的邻居点进行松弛处理dis[j]min(dis[j],dis[node]g[node][j])vis[node]True #对node点标记为已访问
743. 网络延迟时间 因为本题的节点是从1到n所以最后把dis数组中的第一个忽略掉dis[1:]
然后就是经典的dijkstra最短路径算法套用模板即可。
class Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) - int:g[[inf]*(n1) for _ in range(n1)]for x,y,w in times:g[x][y]wdis[inf]*(n1)dis[k]0vis[False]*(n1)for _ in range(n):x-1for i in range(1,n1):if not vis[i] and (x-1 or dis[i]dis[x]):xifor i in range(1,n1):dis[i]min(dis[i],dis[x]g[x][i])vis[x]Trueansmax(dis[1:])return ans if ans!inf else -1 2642. 设计可以求最短路径的图类 又是dijkstra最短路径算法这里需要判断一下能否到达终点的问题
class Graph:def __init__(self, n: int, edges: List[List[int]]):self.nnself.g[[float(INF)]*n for _ in range(self.n)]for x,y,cost in edges:self.g[x][y]costdef addEdge(self, edge: List[int]) - None:self.g[edge[0]][edge[1]]edge[2]def shortestPath(self, node1: int, node2: int) - int:nlen(self.g)dis[float(INF)]*ndis[node1]0vis[False]*nwhile 1:x-1for i,(b,d) in enumerate(zip(vis,dis)):if not b and (x0 or ddis[x]):xiif x0 or dis[x]float(INF):return -1if xnode2:return dis[x]vis[x]Truefor y,w in enumerate(self.g[x]):if dis[x]wdis[y]:dis[y]dis[x]w# Your Graph object will be instantiated and called as such:
# obj Graph(n, edges)
# obj.addEdge(edge)
# param_2 obj.shortestPath(node1,node2) 1334. 阈值距离内邻居最少的城市 枚举每个点作为出发点算法返回小于等于阈值的数目即可。
因为题目要求返回数量最少且编号最大的点所以从n-1到0遍历即可。
class Solution:def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) - int:g[[inf]*n for _ in range(n)]for x,y,w in edges:g[x][y]wg[y][x]w#枚举每个点作为出发点做dijkstra算法def dijkstra(x):dis[inf]*ndis[x]0vis[False]*nfor _ in range(n-1):node-1for j in range(n):if not vis[j] and (node-1 or dis[j]dis[node]):nodejfor j in range(n):dis[j]min(dis[j],dis[node]g[node][j])vis[node]Truereturn sum(ddistanceThreshold for d in dis)ans,cntn,inf for i in range(n-1,-1,-1):if dijkstra(i)cnt:cntdijkstra(i)ansireturn ans
