Dijkstra算法如何跟踪并存储每条最短路径包含的顶点序列

需求说明 #

• 已实现Dijkstra算法核心逻辑，可计算源顶点到其余所有顶点的最短路径距离
• 需要将每条最短路径经过的顶点按顺序存储为数组，所有路径数组统一存入总列表中，要求总列表[顶点编号]直接对应源点到该顶点的路径序列

原代码问题分析 #

原有代码的路径生成逻辑放在了优先队列的循环内部，每次弹出一个顶点就生成路径追加到总列表，会导致三个问题：

1. 优先队列弹出顶点的顺序不是顶点编号的升序，最终总列表的索引和顶点编号无法对应
2. 同一个顶点可能被多次加入优先队列（多次松弛得到更短路径），会导致总列表中出现重复、错误的路径条目
3. visited列表没有在每次调用dijkstra方法时重置，多次调用方法会出现逻辑错误

修复思路 #

1. 保留已经实现的前驱节点记录字典V，用于回溯路径
2. 将路径生成逻辑移到所有松弛操作完成之后，遍历每个顶点回溯前驱链生成路径，保证总列表索引和顶点编号一一对应
3. 每次调用dijkstra方法时先重置visited列表，避免历史数据干扰

修复后完整代码 #

from queue import PriorityQueue

class Graph:
    def __init__(self, num_of_vertices):
        self.v = num_of_vertices
        self.edges = [[-1 for i in range(num_of_vertices)] for j in range(num_of_vertices)]
        
    def add_edge(self, u, v, weight):
        self.edges[u][v] = weight
        self.edges[v][u] = weight
        
    def dijkstra(self, start_vertex):
        # 每次调用先重置访问列表
        self.visited = []
        # D存储各顶点最短距离，V存储各顶点前驱节点
        D = {v:float('inf') for v in range(self.v)}
        V = {v:None for v in range(self.v)}
        D[start_vertex] = 0
        
        pq = PriorityQueue()
        pq.put((0, start_vertex))
        
        while not pq.empty():
            (dist, current_vertex) = pq.get()
            self.visited.append(current_vertex)

            for neighbor in range(self.v):
                if self.edges[current_vertex][neighbor] != -1:
                    distance = self.edges[current_vertex][neighbor]
                    if neighbor not in self.visited:
                        old_cost = D[neighbor]
                        new_cost = D[current_vertex] + distance
                        if new_cost < old_cost:
                            pq.put((new_cost, neighbor))
                            D[neighbor] = new_cost
                            V[neighbor] = current_vertex          
        
        # 所有距离计算完成后统一生成路径
        AllPathsList = []
        for vertex in range(self.v):
            path = []
            u = vertex
            while V[u] != None:
                path.insert(0, u)
                u = V[u]
            path.insert(0, start_vertex)
            AllPathsList.append(path)
            
        return D, AllPathsList
        
def main():
    g = Graph(6)
    g.add_edge(0, 1, 4)
    g.add_edge(0, 2, 7)
    g.add_edge(1, 2, 11)
    g.add_edge(1, 3, 20)
    g.add_edge(3, 4, 5)
    g.add_edge(3, 5, 6)
    g.add_edge(2, 3, 3)
    g.add_edge(2, 4 ,2)
    
    D, AllPathsList = g.dijkstra(0)

    for vertex in range(len(D)):
        print("Distance from vertex 0 to vertex", vertex, "is:", D[vertex])
        print("Particular path is:", AllPathsList[vertex])
main()

运行效果 #

执行代码后输出的路径和顶点编号完全对应，以顶点4为例，输出的路径为[0, 2, 4]，符合最短路径计算结果。

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