python - Dijkstra 算法 - 最短路径中节点的错误顺序

Question

我一直在做一项学校作业，我需要在其中实现 Dijkstra 算法。这本身并不太难，但不幸的是，自动检查脚本与我的所有实现都不一致(我实际上制作了 8 个不同的版本)。所有初始数据检查工作正常，只有当脚本生成随机数据时，它才会有所不同。我的路径和脚本的路径具有相同的距离，但路径上的顶点不同。例如:

Teachers path: City2, City15, City16, City6,

Students path: City2, City15, City18, City0, City6,

我什至联系了刚刚回答“你必须使用优先队列 :-)”的老师，尽管我使用了一个(实际上，一个的几个实现，从我自己的到 heapq)。我做错了什么还是老师的脚本不正确？我希望代码具有足够的 self 注释以便于理解。感谢您给我的任何建议。

该算法在源顶点上调用并计算到每个其他连接节点的最短距离和路径。如果顶点与已经存在的顶点具有相同的 minDistance(即优先级)，则它应该在它的前面，而不是在它之后。

class Node:
    """Basic node of the priority queue"""
    def __init__(self, data, priority):
        self.data = data
        self.nextNode = None
        self.priority = priority
        self.id = data.id

class PriorityQueue:
    """Basic priority queue with add, remove and update methods"""
    def __init__(self):
        self.head = None
        self.count = 0

    def add(self, data, priority):
        """Adds data with priority in the proper place"""
        node = Node(data, priority)
        if not self.head:
            self.head = node
        elif node.priority <= self.head.priority:
            node.nextNode = self.head
            self.head = node
        else:
            checker = self.head
            while True:
                if not checker.nextNode or node.priority >= checker.nextNode.priority:
                    break
                checker = checker.nextNode
            node.nextNode = checker.nextNode
            checker.nextNode = node
        return 0

    def remove(self, data):
        """Removes specified node and reconnects the remaining nodes, does nothing if node not found"""
        checker = self.head
        if not self.head:
            return 0
        if checker.id == data.id:
            self.head = checker.nextNode
        while True:
            checker = checker.nextNode
            if not checker or not checker.nextNode:
                return 0
            if checker.nextNode.id == data.id:
                checker.nextNode = checker.nextNode.nextNode
                break
        return 0

    def update(self, data):
        """Updates priority of existing node via removing and re-adding it"""
        self.remove(data)
        self.add(data, data.minDistance)
        return 0

    def getMin(self):
        """Returns the minimum priority data"""
        min = self.head
        return min.data

class Edge:
    """Edge of the graph, contains source, target and weight of line"""
    def __init__(self, source, target, weight):
        self.source = source
        self.target = target
        self.weight = weight

class Vertex:
    """Vertex of the graph, everything except id and name is filled later"""
    def __init__(self, id, name):
        self.id = id
        self.name = name
        self.minDistance = float('inf')
        self.previousVertex = None
        self.edges = []
        self.visited = False

class Dijkstra:
    """Dijkstra's algorithm implementation"""
    def __init__(self):
        self.vertexes = []
        self.nodes = {}
        self.unvisited = PriorityQueue()

    def createGraph(self, vertexes, edgesToVertexes):
        """Connects edges to appropriate vertexes, adds vertexes to node dictionary"""
        self.vertexes = vertexes
        for vertex in self.vertexes:
            for edge in edgesToVertexes:
                if vertex.id == edge.source:
                    vertex.edges.append(edge)
                    edgesToVertexes.remove(edge)
            self.nodes[vertex.id] = vertex
        return 0

    def getVertexes(self):
        """Returns vertexes in graph, should be called after creating it just to check"""
        return self.vertexes

    def computePath(self, sourceId):
        """Fills in minDistance and previousVertex of all nodes from source"""
        mainNode = self.nodes[sourceId]
        mainNode.minDistance = 0
        self.unvisited.add(mainNode, 0)

        while self.unvisited.head:
            mainNode = self.unvisited.getMin()
            mainNode.visited=True
            for edge in mainNode.edges:
                tempDistance = mainNode.minDistance + edge.weight
                targetNode = self.nodes[edge.target]
                self.unvisited.remove(mainNode)
                if tempDistance < targetNode.minDistance:
                    targetNode.minDistance = tempDistance
                    targetNode.previousVertex = mainNode
                    self.unvisited.update(targetNode)
        return 0

    def getShortestPathTo(self, targetId):
        """Returns list of shortest parth to targetId from source. Call only after doing ComputePath"""
        path = []
        mainNode = self.nodes[targetId]
        while True:
            path.append(mainNode)
            mainNode = mainNode.previousVertex
            if not mainNode:
                break
        return list(reversed(path))

    def resetDijkstra(self):
        """Resets ComputePath but leaves graph untouched"""
        for vertex in self.vertexes:
            vertex.minDistance = float('inf')
            vertex.previousVertex = None
        return 0

Answer 1

def createGraph(self, vertexes, edgesToVertexes):
    """Connects edges to appropriate vertexes, adds vertexes to node dictionary"""
    self.vertexes = vertexes
    for vertex in self.vertexes:
        for edge in edgesToVertexes:
            if vertex.id == edge.source:
                vertex.edges.append(edge)
                edgesToVertexes.remove(edge)
        self.nodes[vertex.id] = vertex
    return 0

我相信这是错误的 => edgesToVertexes.remove(edge)

我有类似的家庭作业并使用了您的一些代码，我认为这一行是不正确的。它在每个循环中从涡流中移除了一条路径。