「堆专题(下)」- dijkstra算法中没有松弛的操作？

[hamuchiwa]

如题

[azl397985856]

首先给出我的代码：

def dijkstra(self, graph, start, end):
        heap = [(0, start)]  # cost from start node,end node
        dist = {}
        while heap:
            (cost, u) = heapq.heappop(heap)
            if u in dist:
                continue
            dist[u] = cost
            for v, c in graph[u]:
                if v in dist:
                    continue
                next = cost + c
                heapq.heappush(heap, (next, v))
        return dist

dijkstra 是以点为基础进行松弛的。dijkstra 将点分为两部分，分别是已经松弛的和没有松弛的，每次从已经松弛的点集中选择一条代价较小的与未松弛的进行连接。

以我的代码来说。 u 就是出度的点，也就是所谓的已经松弛的点。我们需要找所有的未松弛的点进行松弛操作（注意这里的松弛是对点进行松弛，也就是“可能会”松弛 v）。

希望我的回答能够让你满意~