Dijkstra单源最短路径Python实现距离计算错误排查

我正在尝试实现Dijkstra算法，求解源顶点1到所有其他顶点的最短距离，具体实现代码如下：

from ast import literal_eval


p = {}
with open(r'dijk.txt') as file:
    for line in file:
            line_content = line.split()
            p[int(line_content[0])] = [literal_eval(edge) for edge in line_content[1:]]
    source_vertex = next(iter(p.keys()))


print("Vertex 1's paths:", p[1])
print("1st value for vertex 1:", p[1][0])
print("1st neighbour of vertex 1:",p[1][0][0])
print("Distance of 1st neighbour of vertex 1:",p[1][0][1])


X = [1]
Y = [1]
A = {}
A[1] = 0
for i in range(2,201):
    A[i] = 100000000
    Y.append(i)


while X != Y:
    b = {}
    for eachvertex in X:
        b2 = 0
        for eachneighbour in p[eachvertex]:
            if eachneighbour[0] not in X:
                b2 = A[eachvertex]+eachneighbour[1]
                b[eachneighbour[0]] = b2
    vertex_to_be_added = min(b, key = b.get)
    X.append(vertex_to_be_added)
    A[vertex_to_be_added] = min(b.values())
    print("Vertex added :",vertex_to_be_added, "and distance :",min(b.values()))
    X.sort()

本次测试使用的数据源可通过链接获取：LinkToData

该代码在while循环第一次迭代时运行正常，但后续迭代计算得到的新增顶点最短距离结果不正确。

代码共有两处直接导致结果错误的逻辑问题：

• 跨集合边的距离值被随意覆盖
  每次循环都会重新初始化空字典b，遍历已加入最短路径集合X的所有顶点的出边时，只要边的另一端不在X中，就直接把计算出的距离写入b，完全不判断这个邻居顶点是否已经在b里存了更小的候选距离。
  举个例子：顶点2、3都已在X中，两者都连向未加入X的顶点4：从顶点2到4的候选距离是10，从顶点3到4的候选距离是5。如果遍历顺序是先处理顶点2再处理顶点3，b[4]会先被赋值10，再被更小的5覆盖，结果暂时正确；但如果遍历顺序反过来，先处理顶点3算出距离5，再处理顶点2算出距离10，原本更小的5就会被10覆盖，直接导致后续选最小距离出错。
  正确逻辑是：计算出到未入集合邻居的距离后，只有当该邻居不在b中，或者新计算的距离比b中已存的距离更小时，才更新b里的值，否则保留原有更小的距离。
• 新顶点的最短距离赋值错误
  选出本轮要加入X的顶点后，代码直接给该顶点的最短距离A[vertex_to_be_added]赋值为min(b.values())，也就是整个b字典里的全局最小值，这是完全错误的。min(b.values())只对应本轮所有候选顶点里距离最小的那个值，不是当前选中顶点自己的候选距离。比如本轮b中顶点4的候选距离是5、顶点5的候选距离是3，全局最小值3对应顶点5，选中顶点5加入时赋值3是对的；但如果后续轮次里b中顶点4的候选距离是10、顶点6的候选距离是2，全局最小值是2对应顶点6，此时如果选中顶点4加入，代码会错误把顶点4的距离赋值为2，结果完全错乱。
  正确逻辑是：新顶点加入X时，它的最短距离直接取b[vertex_to_be_added]，也就是该顶点自己在候选字典里对应的距离值即可。

另外循环内定义的b2 = 0没有任何实际作用，可以直接删除。

while X != Y:
    b = {}
    for eachvertex in X:
        for eachneighbour in p[eachvertex]:
            neighbor_id = eachneighbour[0]
            if neighbor_id not in X:
                current_dist = A[eachvertex] + eachneighbour[1]
                # 仅当邻居无记录或新距离更小时才更新候选值
                if neighbor_id not in b or current_dist < b[neighbor_id]:
                    b[neighbor_id] = current_dist
    vertex_to_be_added = min(b, key = b.get)
    X.append(vertex_to_be_added)
    # 赋值为当前顶点对应的候选距离
    A[vertex_to_be_added] = b[vertex_to_be_added]
    print("Vertex added :", vertex_to_be_added, "and distance :", A[vertex_to_be_added])
    X.sort()

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