Dijkstra算法相关技术问题咨询：顶点标记、终止时机及decrease-key用法

1. 何时标记顶点为已访问并确定最短路径？ #

当你从优先队列（最小堆）中取出当前距离起点最短的顶点u时，就可以标记u为已访问，并且确定此时u的距离就是起点到它的最短路径。
原因很简单：Dijkstra算法要求所有边的权重都是非负数。此时队列中剩余的所有未访问顶点，它们当前记录的距离都大于等于u的距离。如果存在一条经过其他未访问顶点到u的更短路径，那这条路径的最后一步必然是从某个未访问顶点v到u，而v的当前距离加上边v-u的权重（非负）肯定会大于等于u的当前距离，不可能得到更短的路径。所以u的最短路径已经确定，无需再处理。

2. 寻找两点间最短路径时何时停止搜索？ #

当你从优先队列中取出的顶点恰好是目标顶点时，就可以直接停止搜索。
根据第一个问题的结论，此时目标顶点的最短路径已经确定，继续处理其他顶点完全是多余的，直接终止算法即可。

3. 为什么用decrease-key而非重复加入邻接顶点？如何实现？ #

核心原因 #

如果每次更新邻接顶点v的距离时，都把(v, 新距离)加入优先队列，队列中会出现同一个顶点的多个条目（对应不同的距离值）。后续处理到旧的、距离更大的条目时，因为顶点已经被标记为已访问，只能跳过，这会浪费队列的存储空间和处理时间。
而decrease-key操作的本质是：当找到顶点v的更短路径时，直接更新优先队列中v对应条目的优先级（即距离值），而不是新增条目，这样队列中始终只有每个顶点的最新、最短距离条目，效率更高。

实现思路 #

要实现decrease-key，需要使用支持该操作的优先队列，比如二叉堆（需额外维护顶点位置）或斐波那契堆（原生支持但实现复杂）。这里以二叉堆为例，给出关键步骤：

1. 维护一个最小堆，堆中元素为(当前最短距离, 顶点)。
2. 维护一个position数组，记录每个顶点在堆中的索引位置，方便快速定位。
3. 当计算出顶点v的新距离new_dist小于当前记录的距离时：
   • 找到v在堆中的索引idx = position[v]。
   • 修改堆中idx位置的元素为(new_dist, v)。
   • 执行上浮操作（sift up）：将修改后的元素向上调整，直到堆的性质（父节点距离小于子节点）恢复，同时更新position数组中涉及的顶点位置。

以下是简化的Python代码片段（仅展示核心逻辑）：

def sift_up(heap, pos, idx):
    while idx > 0:
        parent = (idx - 1) // 2
        if heap[idx][0] < heap[parent][0]:
            # 交换父节点和当前节点
            heap[idx], heap[parent] = heap[parent], heap[idx]
            # 更新位置记录
            pos[heap[idx][1]] = idx
            pos[heap[parent][1]] = parent
            idx = parent
        else:
            break

# 假设已经初始化了dist数组（记录各顶点的最短距离）、heap、pos数组
# 当找到v的更短路径new_dist时：
if new_dist < dist[v]:
    dist[v] = new_dist
    # 找到v在堆中的位置
    idx = pos[v]
    # 更新堆中的距离值
    heap[idx] = (new_dist, v)
    # 上浮调整堆
    sift_up(heap, pos, idx)

注意：Python标准库的heapq模块不直接支持decrease-key，所以实际项目中如果追求简单，很多时候会采用“重复加入队列+跳过已访问顶点”的方式，虽然效率略低，但实现成本低。如果追求高效，就需要自己实现带decrease-key的堆结构。

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