Dijkstra算法变体的性能分析及相关疑问解答请求

首先给出该算法的完整Python实现（补充类型定义以保证可运行性）：

"""
Graph 是通过字典实现的邻接表
"""

from collections import deque
from typing import Dict

# 定义Graph类型
Graph = Dict[str, Dict[str, float]]

def dijkstra(graph: Graph, start: str) -> Dict[str, float]:
    queue = deque()
    shortest_distances = dict()
    shortest_distances[start] = 0
    queue.append(start)
    while queue:
        vertex = queue.popleft()
        for neighbour in graph[vertex]:
            edge_weight = graph[vertex][neighbour]
            parent_weight = shortest_distances[vertex]
            existing_weight = shortest_distances.get(neighbour, float('inf'))
            
            if existing_weight == float('inf') or \
                parent_weight + edge_weight < existing_weight:
                shortest_distances[neighbour] = parent_weight + edge_weight
                queue.append(neighbour)
            
    return shortest_distances

以下是针对该算法的技术疑问解答：

问题1：仅存在非负权边时，该算法的最坏时间复杂度是多少？原因是什么？ #

最坏时间复杂度为 O(N·E)，其中N是顶点数，E是边数。若为稠密图（E=O(N²)），则复杂度为 O(N³)。
原因分析：
在非负权图中，每个顶点的最短距离最多被更新O(N)次——非负权边的特性决定了，路径边数越多，总权重不会小于边数更少的路径，但极端情况下，某个顶点可能通过不同长度的路径被多次更新（例如存在多条路径到该顶点，每条路径的总权重依次递减）。每次更新都会将顶点入队，每个顶点入队O(N)次，每次入队后会遍历其所有邻接边，总操作数为O(N·E)。
注：你直觉中的O(N²)是标准Dijkstra算法（用数组每次选最小距离顶点）的时间复杂度，而该变体用普通队列，最坏情况复杂度更高。

问题2：存在负权边但无负权环时，该算法的最坏时间复杂度是多少？原因是什么？ #

最坏时间复杂度为 指数级O(2^N)。
原因分析：
在无负权环但含负权边的图中，更长的路径（边数更多）可能拥有更小的总权重，这会导致顶点的最短距离被反复更新。可以构造特定图结构，使得每次更新一个顶点都会触发一系列其他顶点的更新，队列中的顶点数量呈指数级增长。例如，设计链式图，每个中间顶点到后续顶点设负权边，同时起点到每个顶点设递减权值边，使得每个顶点的更新次数随顶点数指数增加，最终导致算法时间复杂度爆炸。

问题3：上述两种场景的性能是否存在差异？若存在，原因是什么？ #

存在显著差异。
核心原因在于边权的非负性限制：

• 非负权场景下，一旦某个顶点的最短距离确定（达到最小值），后续不可能通过任何路径得到更小的距离（新增边权非负，总权重只会更大），因此每个顶点的更新次数被限制在O(N)以内，总操作数可控。
• 负权边场景下，更长的路径可能带来更小的总权重，顶点的最短距离会被反复更新，甚至出现指数级的更新次数，导致算法性能急剧下降。

问题4：该变体算法与Bellman-Ford、Floyd-Warshall等同类算法的性能相比如何？ #

与Bellman-Ford对比 #

• Bellman-Ford的最坏时间复杂度稳定在O(N·E)，即使在负权边无负权环的场景下也能保证这个上界，而该变体在负权场景下最坏是指数级，稳定性远不如Bellman-Ford。
• 在非负权场景下，该变体的平均性能可能优于Bellman-Ford（实际中顶点更新次数往往远少于N次），但最坏复杂度与Bellman-Ford相当，且远不如用优先队列实现的标准Dijkstra算法（O(E log N)）。

与Floyd-Warshall对比 #

• Floyd-Warshall是全源最短路径算法，时间复杂度固定为O(N³)；该变体是单源算法，在稀疏图非负权场景下的最坏复杂度O(N·E)（远小于O(N³)）有一定优势，但稠密图下最坏复杂度与Floyd-Warshall相当。
• 在负权边场景下，该变体的指数级最坏复杂度远不如Floyd-Warshall的稳定O(N³)。

总结 #

该变体仅在非负权稀疏图、实际更新次数少的场景下有一定实用价值，但稳定性差，无法处理负权环，性能上限远低于标准优先队列版Dijkstra，也不如Bellman-Ford、Floyd-Warshall在负权场景下的可靠性。

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