[TOC]
Dijkstra1
朴素（稠密图）
class Graph:
def __init__(self, n: int, edges: List[List[int]]):
self.g = [[inf]*n for _ in range(n)]
for x,y,w in edges:
self.g[x][y] = w
def addEdge(self, edge: List[int]) -> None:
x,y,w = edge
self.g[x][y]=w
def shortestPath(self, node1: int, node2: int) -> int:
n = len(self.g)
dis = [inf]*n
vis = [False]*n
dis[node1] = 0
while True:
x=-1
for i,(b,d) in enumerate(zip(vis,dis)):
if not b and (x<0 or d<dis[x]):
x=i
if x<0 or dis[x]==inf:
return -1
if x==node2:
return dis[x]
vis[x]=True
for y,w in enumerate(self.g[x]):
if dis[x]+w<dis[y]:
dis[y]=dis[x]+w
时间复杂度：
- 初始化：O(n^2)
- addEdge: O(1)
- shortestPath: O(n^2)
空间复杂度：O(n^2)
堆优化（稀疏图、平面图）
class Graph:
def __init__(self, n: int, edges: List[List[int]]):
self.g = [[] for _ in range(n)]
for x,y,w in edges:
self.g[x].append((y,w))
def addEdge(self, edge: List[int]) -> None:
x,y,w = edge
self.g[x].append((y,w))
def shortestPath(self, node1: int, node2: int) -> int:
n = len(self.g)
dis = [inf]*n
dis[node1] = 0
h = [(0,node1)]
while h:
d,x = heappop(h)
if x==node2:
return d
if d>dis[x]:
continue
for y,w in self.g[x]:
if dis[x]+w<dis[y]:
dis[y]=dis[x]+w
heappush(h,(dis[y],y))
return -1
时间复杂度：
- 初始化：O(m+n)
- addEdge: O(1)
- shortestPath: O(n+mlogm)
空间复杂度：O(m+n)
Floyd
题单
Reference
-
https://leetcode.cn/problems/design-graph-with-shortest-path-calculator/?envType=daily-question&envId=2024-03-26 ↩
