求助：针对固定数量权重优化Dijkstra算法的线性时间实现

当图中唯一边权重的数量C是常数时，核心思路是用**桶队列（Bucket Queue）**替代Dijkstra算法中传统的二叉堆/斐波那契堆，利用权重种类有限的特性，把优先队列操作的时间复杂度降到分摊O(1)，最终实现线性时间O(V + E)的求解。

具体实现步骤： #

• 预处理边权重：遍历所有边，收集所有唯一的权重值，排序得到有序列表 w₁ < w₂ < ... < w_C。额外新增一个对应距离0的桶（如果源点初始距离0不在已有的权重列表中）。
• 初始化距离数组：设源点为s，dist[s] = 0，将s放入对应距离0的桶中；其余节点dist[v] = ∞，暂不放入任何桶。
• 维护当前最小有效桶：
  1. 从最小权重的桶开始遍历（最多遍历C+1个桶，C是常数，这一步分摊时间为O(1)），找到第一个非空的桶。
  2. 从该桶中取出队首节点u，如果dist[u]不等于当前桶对应的权重值，说明这个节点已经被更新过更短的距离，直接跳过（延迟删除策略）。
• 松弛邻边：
  对节点u的每条出边(u, v)，计算新距离new_dist = dist[u] + c(u, v)。
  • 如果new_dist < dist[v]：更新dist[v] = new_dist，将v放入对应new_dist值的桶中（无需删除v之前所在的桶，后续取出时会自动跳过无效的旧条目）。
• 重复上述步骤，直到所有桶都为空，此时dist数组就是源点到所有节点的最短距离。

时间复杂度分析 #

• 每个节点仅会被有效处理一次（即取出时dist[u]等于桶的权重），其余放入桶的条目都会被延迟删除跳过。
• 每条边只会被松弛一次，松弛操作中的桶入队是O(1)。
• 遍历桶找最小非空桶的操作，因C是常数，每次遍历时间为O(1)，总遍历次数在O(V + E)级别，分摊后不影响线性时间。
  最终整体时间复杂度为O(V + E)，达到线性时间要求。

内容的提问来源于stack exchange，提问作者Chees3FNA