Python：堆化元组列表（Dijkstra 算法）

Question

这是我的 Dijkstra 算法代码。我已经声明了一个“顶点”class 和一个“图形”class。我正在使用 heapq 模块并堆放元组列表“unvisitedQueue”。但即便如此，即使“v.getDistance()”returns 为 0 或浮动（'inf'）。

import heapq

class Vertex:
    def __init__(self, node):
        self.id = node
        self.adjacent = {}
        self.previous = None
        self.distance = float('inf')
    
    def addNeighbor(self, neighbor, weight = 0):
        self.adjacent[neighbor] = weight
    
    def getConnections(self):
        return self.adjacent.keys()
    
    def getVertex_ID(self):
        return self.id
    
    def getWeight(self, neighbor):
        return self.adjacent[neighbor]

    def setDistance(self, dist):
        self.distance = dist

    def getDistance(self):
        return self.distance

    def setPrevious(self, prev):
        self.previous = prev

    def __str__(self):
        return str(self.id) + "adjacent : " + str([x.id for x in self.adjacent])
    
class Graph:
    def __init__(self):
        self.vertDictionary = {}
        self.numVertices = 0
    
    def __iter__(self):
        return iter(self.vertDictionary.values())
    
    def addVertex(self, node):
        self.numVertices += 1
        newVertex = Vertex(node)
        self.vertDictionary[node] = newVertex
        return newVertex
    
    def getVertex(self, node):
        if node in self.vertDictionary:
            return self.vertDictionary[node]
        else:
            return None
    
    def addEdge(self, frm, to, cost = 0):
        if frm not in self.vertDictionary:
            self.addVertex(frm)
        if to not in self.vertDictionary:
            self.addVertex(to)
        self.vertDictionary[frm].addNeighbor(self.vertDictionary[to], cost)
        
        self.vertDictionary[to].addNeighbor(self.vertDictionary[frm], cost)
    
    def getVertices(self):
        return self.vertDictionary.keys()
    
    def setPrevious(self, current):
        self.previous = current
    
    def getPrevious(self):
        return self.previous
    
    def getEdges(self):
        edges = []
        for v in G:
            for w in v.getConnections():
                v_id = v.getVertex_ID()
                w_id = w.getVertex_ID()
                edges.append((v_id, w_id, v.getWeight(w)))
        return edges
def Dijkstra(G, s):
    source = G.getVertex(s)
    source.setDistance(0)
    visited = {}
    unvisitedQueue = [(v.getDistance(), v) for v in G]
    heapq.heapify(unvisitedQueue)
    while len(unvisitedQueue):
        uv = heapq.heappop(unvisitedQueue)
        currVert = uv[1]
        visited[currVert] = True
        for nbr in currVert.getConnections():
            if currVert.getDistance() + currVert.getWeight(nbr) < nbr.getDistance():
                nbr.setDistance(currVert.getDistance() + currVert.getWeight(nbr))
                print("Updated: Current = %s Neighbour = %s New Distance = %s" %(currVert.getVertex_ID(), nbr.getVertex_ID(), nbr.getDistance()))
            else:
                print("Not Updated: Current = %s Neighbour = %s Distance = %s" %(currVert.getVertex_ID(), nbr.getVertex_ID(), nbr.getDistance()))
        while len(unvisitedQueue):
            heapq.heappop(unvisitedQueue)
        unvisitedQueue = [(v.getDistance(), v) for v in G if v not in visited]
        heapq.heapify(unvisitedQueue)
    for v in G:
        print(source.getVertex_ID(), "to", v.getVertex_ID(), "-->", v.getDistance())

错误 -->

Traceback (most recent call last):
  File "d:\Python\Final 450\Graph\Dijkstra's_Algo.py", line 124, in <module>
    print(Dijkstra(G, "a"))
  File "d:\Python\Final 450\Graph\Dijkstra's_Algo.py", line 86, in Dijkstra 
    heapq.heapify(unvisitedQueue)
TypeError: '<' not supported between instances of 'Vertex' and 'Vertex'

Answer 1

错误发生是因为元组是按字典序比较的。如果两个距离相同，则比较移动到 Vertex 对象本身。

很容易想到两种解决方案。第一种是简单地在 Vertex 之前但在距离之后向元组添加唯一索引。这很简单，即使您无法访问 Vertex class:

也能正常工作

unvisitedQueue = [(v.getDistance(), i, v) for i, v in enumerate(G) if v not in visited]

第二个方案是修改Vertex有一个__lt__魔术方法：

def __lt__(self, other):
    return self.getDistance() < other.getDistance()

这很好，因为您现在可以更直接地堆化：

unvisitedQueue = [v for v in G if v not in visited]

Python：堆化元组列表（Dijkstra 算法）

Python: Heapify a list of tuples (Dijkstra's Algo)

python

list

tuples

heap

dijkstra