基于邻接表的无向加权图最短路径：非优先队列实现的顺序问题

我基于邻接表实现了无向加权图的最短路径函数，没用到优先队列，目标是计算并展示起始节点的最短路径。现在能算出从节点A出发的最短路径，但节点输出顺序和预期不符，想问下是否应该改用优先队列实现？

预期输出 #

B(4) C(12) D(19) E(21) F(11) G(9) H(8) I(14) J(inf)

实际输出 #

B(4) H(8) C(12) G(9) I(14) D(19) F(11) E(21)

邻接表 #

• A- {'B': 4, 'H': 8}
• B- {'A': 4, 'C': 8, 'H': 11}
• C- {'B': 8, 'D': 7, 'F': 4, 'I': 2}
• D- {'C': 7, 'E': 9, 'F': 14}
• E- {'D': 9, 'F': 10}
• F- {'C': 4, 'D': 14, 'E': 10, 'G': 2}
• G- {'F': 2, 'H': 1, 'I': 6}
• H- {'A': 8, 'B': 11, 'G': 1, 'I': 7}
• I- {'C': 2, 'G': 6, 'H': 7}
• J- {}

实现代码 #

class WGraph:
    def __init__(self, size=10):
        self.size = 10
        self.nodeList = {}
        self.adjacencyMatrix = [[0] * size for i in range(size)]  # initialize matrix

    def addNode(self, name):
        """Adds node to adjacency list"""
        self.nodeList[name] = {}

    def addEdge(self, startIndex, endIndex, weight):
        """Add edges for adjacency list and matrix"""
        self.nodeList[startIndex][endIndex] = weight
        self.nodeList[endIndex][startIndex] = weight

        index1 = list(self.nodeList.keys()).index(startIndex)
        index2 = list(self.nodeList.keys()).index(endIndex)
        self.adjacencyMatrix[index1][index2] = weight

    def displayAdjacency(self):
        """Displays adjacency list with edges and weight"""
        for node in self.nodeList:
            print(node + "- " + str(self.nodeList[node]))


    def minCostPaths(self, vertex):
        visited = {vertex: 0}
        queue = [(vertex, 0)]
        while queue:
            node, cost = queue.pop(0)
            for neighbor in self.nodeList[node]:
                if neighbor not in visited or cost + self.nodeList[node][neighbor] < visited[neighbor]:
                    visited[neighbor] = cost + self.nodeList[node][neighbor]
                    queue.append((neighbor, cost + self.nodeList[node][neighbor]))
        output = ""
        for node in visited:
            if node != vertex:
                output += f"{node}({visited[node]}) "
        return output[:-2] + ")"


# Driver Code
graph = WGraph()

graph.addNode('A')
graph.addNode('B')
graph.addNode('C')
graph.addNode('D')
graph.addNode('E')
graph.addNode('F')
graph.addNode('G')
graph.addNode('H')
graph.addNode('I')
graph.addNode('J')

graph.addEdge('A', 'B', 4)
graph.addEdge('A', 'H', 8)
graph.addEdge('B', 'C', 8)
graph.addEdge('B', 'H', 11)
graph.addEdge('C', 'D', 7)
graph.addEdge('C', 'F', 4)
graph.addEdge('C', 'I', 2)
graph.addEdge('D', 'E', 9)
graph.addEdge('D', 'F', 14)
graph.addEdge('E', 'F', 10)
graph.addEdge('F', 'G', 2)
graph.addEdge('G', 'H', 1)
graph.addEdge('G', 'I', 6)
graph.addEdge('H', 'I', 7)

graph.displayAdjacency()

print("The minimum cost paths starting at A ")
print(" Expected B(4) C(12) D(19) E(21) F(11) G(9) H(8) I(14) J(inf) ")
print(" Actually " + graph.minCostPaths('A'), end="\n")

1. 输出顺序问题的本质 #

你当前的输出顺序是节点被首次访问的顺序，而预期输出是节点名称的字典序（B、C、D、E、F、G、H、I、J），这和是否使用优先队列无关。优先队列的作用是优化最短路径算法的时间复杂度（从类Bellman-Ford的O(V+E)，优化为Dijkstra的O(E log V)），但不会直接改变最终输出的节点排序。

2. 如何修正输出顺序 #

要得到预期的输出顺序，只需在生成结果时，按照节点名称的字典序遍历所有节点即可，同时还要处理未被访问到的J节点（需手动标记为inf）。

修改minCostPaths函数的输出部分：

def minCostPaths(self, vertex):
    visited = {vertex: 0}
    queue = [(vertex, 0)]
    while queue:
        node, cost = queue.pop(0)
        for neighbor in self.nodeList[node]:
            if neighbor not in visited or cost + self.nodeList[node][neighbor] < visited[neighbor]:
                visited[neighbor] = cost + self.nodeList[node][neighbor]
                queue.append((neighbor, cost + self.nodeList[node][neighbor]))
    # 按节点名称字典序排序，遍历所有节点
    all_nodes = sorted(self.nodeList.keys())
    output = ""
    for node in all_nodes:
        if node != vertex:
            cost = visited.get(node, float('inf'))
            # 处理inf的显示格式
            cost_str = str(cost) if cost != float('inf') else "inf"
            output += f"{node}({cost_str}) "
    # 去掉末尾多余的空格
    return output.strip()

3. 是否需要改用优先队列？ #

• 如果你的图规模较小（比如当前的10个节点），当前的实现完全够用，不需要改优先队列。
• 如果图的节点和边数量很大，优先队列实现的Dijkstra算法会有明显的性能优势，此时建议替换。

另外，当前代码的队列处理逻辑存在重复入队的问题（同一个节点可能被多次加入队列），虽然不影响结果正确性，但会降低效率。如果要优化，不管用不用优先队列，都可以考虑标记节点是否已经达到最优状态，避免重复操作。

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