难度: Hard
Submission
运行时间: 848 ms
内存: 21.0 MB
class Solution:
def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:
adjList = [[] for _ in range(n)]
for u, v, w in edges:
adjList[u].append((v, w))
adjList[v].append((u, w))
dist = [[inf] * (k + 1) for _ in range(n)]
dist[s][0] = 0
pq = [(0, s, 0)] # (dist, node, hops)
while pq:
curDist, curNode, curHops = heappop(pq)
if curDist > dist[curNode][curHops]:
continue
for next, weight in adjList[curNode]:
cand1 = curDist + weight
if cand1 < dist[next][curHops]:
dist[next][curHops] = cand1
heappush(pq, (cand1, next, curHops))
cand2 = curDist
if curHops + 1 <= k and cand2 < dist[next][curHops + 1]:
dist[next][curHops + 1] = cand2
heappush(pq, (cand2, next, curHops + 1))
return min(dist[d])
Explain
该题解采用了优先队列（最小堆）结合动态规划的方法在图中寻找从起点到终点的最短路径，同时限制路径中的跳数不超过K次。首先构建每个节点的邻接表来表示图。定义一个二维数组 dist，其中 dist[i][j] 表示从起点 s 到节点 i 使用 j 次跳的最短距离。初始化所有距离为无穷大，只有起点 s 在跳数为0的情况下距离为0。使用优先队列来存储当前的节点、距离及已经使用的跳数。每次从队列中取出距离最小的节点进行扩展，更新通过该节点可能达到的邻接节点的最短距离。如果通过当前节点直接到达邻接节点的距离小于已记录的距离，或者通过当前节点跳转到邻接节点（增加一次跳数）的情况下距离更短，则更新相应的距离并将该状态加入队列中。最后，从 dist 数组中的终点 d 相关的所有跳数中选取最小的距离返回。
时间复杂度: O(n*k*log(n*k))
空间复杂度: O(E + n*k)
class Solution:
def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:
# 创建邻接表
adjList = [[] for _ in range(n)]
for u, v, w in edges:
adjList[u].append((v, w))
adjList[v].append((u, w)) # 因为是无向图
# 初始化距离数组
dist = [[inf] * (k + 1) for _ in range(n)]
dist[s][0] = 0
pq = [(0, s, 0)] # (dist, node, hops)
while pq:
curDist, curNode, curHops = heappop(pq) # 获取当前最短距离的节点
if curDist > dist[curNode][curHops]: # 如果当前节点的距离已经不是最小，跳过
continue
for next, weight in adjList[curNode]:
cand1 = curDist + weight # 直接到达邻接节点
if cand1 < dist[next][curHops]: # 更新距离并入队
dist[next][curHops] = cand1
heappush(pq, (cand1, next, curHops))
cand2 = curDist # 不增加跳数，仅考虑跳数增加的情况
if curHops + 1 <=k and cand2 < dist[next][curHops + 1]: # 考虑增加跳数的情况
dist[next][curHops + 1] = cand2
heappush(pq, (cand2, next, curHops + 1))
return min(dist[d]) # 从所有可能的跳数中选择最小距离
Explore
在初始化`dist`数组时，将起点的距离设置为0是因为从起点到起点的距离自然为0（无需任何移动）。这是迪杰斯特拉算法和其他图的最短路径算法的一部分标准操作，确保算法从起点开始扩散，逐步通过每个边更新到其他所有节点的最短路径。如果起点的初始距离被设置为无穷大，那么算法将无法启动，因为没有节点可以从起点以0的成本到达。这种初始化确保了算法的正确流向和正确性，允许它从逻辑上正确地评估从起点到图中其他点的距离。
优先队列（在Python中通常通过`heapq`模块实现）自动维护了一个最小堆的数据结构，该数据结构保证了堆顶（或队列的开始）始终是最小元素。当新的元素被添加到优先队列中时，它会自动比较并调整位置以维持最小堆的性质，这意味着不需要手动进行比较。每次从优先队列中取出元素（使用`heappop`），都会从队列中移除并返回最小元素，同时重新调整堆以保持其最小堆的性质。这个机制保证了每次取出的都是当前已知最短距离的节点，从而使算法能够有效地进行。
这种情况发生的原因是同一个节点可能以不同的总距离被多次添加到优先队列中。在算法执行过程中，当一个节点的最短距离被更新后，这个更新的距离（较小值）和该节点会被添加到队列中。如果此前这个节点已经以更长的距离存在于队列中，就会出现队列中有同一节点但带有不同距离的情况。当从队列中取出节点时，我们检查该节点的当前距离是否仍然是队列中保存的距离。如果不是（即已经找到了一条更短的路径到达该节点），我们就跳过这个节点，因为其基于的距离信息已经过时。这种机制防止了算法在已经找到更优解后浪费时间处理无效或过时的路径。