【更新中】Leetcode中遇到的最短路径算法

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]):node=jfor 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]*(n+1) for _ in range(n+1)]for x,y,w in times:g[x][y]=wdis=[inf]*(n+1)dis[k]=0vis=[False]*(n+1)for _ in range(n):x=-1for i in range(1,n+1):if not vis[i] and (x==-1 or dis[i]<dis[x]):x=ifor i in range(1,n+1):dis[i]=min(dis[i],dis[x]+g[x][i])vis[x]=Trueans=max(dis[1:])return ans if ans!=inf else -1

2642. 设计可以求最短路径的图类
又是dijkstra最短路径算法，这里需要判断一下能否到达终点的问题：

class Graph:def __init__(self, n: int, edges: List[List[int]]):self.n=nself.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:n=len(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 (x<0 or d<dis[x]):x=iif x<0 or dis[x]==float('INF'):return -1if x==node2:return dis[x]vis[x]=Truefor y,w in enumerate(self.g[x]):if dis[x]+w<dis[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]):node=jfor j in range(n):dis[j]=min(dis[j],dis[node]+g[node][j])vis[node]=Truereturn sum(d<=distanceThreshold for d in dis)ans,cnt=n,inf    for i in range(n-1,-1,-1):if dijkstra(i)<cnt:cnt=dijkstra(i)ans=ireturn ans