使用类实现python dijkstra算法可能存在的问题

Question

因此，我一直在尝试用python创建一个图形程序，其中的类实现了dfs、bfs和dijkstra的算法，到目前为止，我已经提出了：

class Vertex:
    def __init__(self, name):
        self.name = name
        self.connections = {}

    def addNeighbour(self, neighbour, cost):
        self.connections[neighbour] = cost


class Graph:
    def __init__(self):
        self.vertexs = {}

    def addVertex(self, newVertex):
        new = Vertex(newVertex)
        self.vertexs[newVertex] = new

    def addEdge(self, src, dest, cost):
        self.vertexs[src].addNeighbour(self.vertexs[dest], cost)

    def dfs(self, start, end, visited):
        visited[start] = True
        print(start, end=' ')
        if start == end:
            # End node found
            return True
        else:
            # Use depth first search
            for connection in graph.vertexs[start].connections:
                if visited[connection.name] == False:
                    if self.dfs(connection.name, end, visited) == True:
                        # Return true to stop extra nodes from being searched
                        return True

    def bfs(self, start, end, visited, queue):
        if len(queue) == 0:
            # Queue is empty
            queue.append(start)
        visited[start] = True
        currentNode = queue.pop(0)
        print(currentNode, end=' ')
        if start == end:
            # End node found
            return True
        else:
            # Do breadth first search
            for connection in graph.vertexs[currentNode].connections:
                if visited[connection.name] == False:
                    # Queue all its unvisited neighbours
                    queue.append(connection.name)
            for newNode in queue:
                self.bfs(newNode, end, visited, queue)

    def dijkstra(self, current, currentDistance, distances, visited, unvisited):
        for neighbour, distance in distances.items():
            if neighbour.name not in unvisited:
                continue
            newDistance = currentDistance + distance
            if unvisited[neighbour.name] is None or unvisited[neighbour.name] > newDistance:
                unvisited[neighbour.name] = newDistance
        visited[current] = currentDistance
        del unvisited[current]
        if not unvisited:
            return True
        candidates = [node for node in unvisited.items() if node[1]]
        current, currentDistance = sorted(candidates)[0]
        self.dijkstra(current, currentDistance, graph.vertexs[current].connections, visited, unvisited)
        return visited


def setup():
    graphList = {
        # Node number: [destination number, cost]
        0: {4: 6, 6: 1},
        1: {6: 2},
        2: {0: 9, 1: 4, 3: 3},
        3: {4: 7},
        4: {1: 3, 5: 5},
        5: {0: 2, 1: 6, 4: 3},
        6: {2: 4, 3: 6}
    }
    graph = Graph()

    for i in range(len(graphList)):
        graph.addVertex(i)

    for dictLength in range(len(graphList)):
        for key in list(graphList[dictLength].keys()):
            graph.addEdge(dictLength, key, graphList[dictLength][key])
    return graph, graphList


graph, graphList = setup()


print("DFS travsersal path from node 1 to node 0:")
graph.dfs(1, 0, [False] * len(graphList))
print()

print("BFS traversal path from node 1 to node 0:")
graph.bfs(1, 0, [False] * len(graphList), [])
print()

print("Shortest possible path from node 1 to 0:")
result = graph.dijkstra(1, 0, graph.vertexs[2].connections, {}, {node: None for node in graphList})
cost = result[len(result) - 1]
path = " ".join([str(arrInt) for arrInt in list(result.keys())])
print(path, "costing", cost)

但我认为输出似乎有问题。如果我想从节点1移动到节点0，则当前输出为：

DFS travsersal path from node 1 to node 0: 1 6 2 0 BFS traversal path from node 1 to node 0: 1 6 2 3 0 3 4 5 Shortest possible path from node 1 to 0: 1 0 3 4 5 6 2 costing 10

但是，我认为输出应该是：

DFS travsersal path from node 1 to node 0: 1 6 2 0 4 5 3 BFS traversal path from node 1 to node 0: 1 6 2 3 0 4 5 Shortest possible path from node 1 to 0: 1 6 2 0 costing 15

有人看到这有什么问题吗

谢谢

Answer 1

实际上，代码中有几个问题：

1. 您需要为Djikstra的算法指定停止的位置，在代码中没有提到什么是结束节点（在您的示例中，它应该是0）

2. 将成本计算为cost = result[len(result) - 1]并不能得到字典中的最后一个元素（字典通常没有排序，因此“最后一个元素”甚至不存在！）。您应该将成本检索为cost = result[end]，其中end是最后一个节点，在您的示例中为0

3. 您正在以result = graph.dijkstra(1, 0, graph.vertexs[2].connections, {}, {node: None for node in graphList})的形式调用该函数，但是，该函数的第三个参数应该是初始节点的邻居集，因此在本例中它应该是graph.vertexs[1].connections

总之，要使代码按预期工作，可以按如下方式修改函数：

def dijkstra(self, current, currentDistance, distances, visited, unvisited, end):
    for neighbour, distance in distances.items():
        if neighbour.name not in unvisited:
            continue
        newDistance = currentDistance + distance
        if unvisited[neighbour.name] is None or unvisited[neighbour.name] > newDistance:
            unvisited[neighbour.name] = newDistance
    visited[current] = currentDistance

    if current == end:
      return visited

    del unvisited[current]
    if not unvisited:
        return True
    candidates = [node for node in unvisited.items() if node[1]]
    current, currentDistance = sorted(candidates)[0]
    
    self.dijkstra(current, currentDistance, graph.vertexs[current].connections, visited, unvisited, end)
    return visited

并称之为：

print("Shortest possible path from node 1 to 0:")
start = 1
end = 0
result = graph.dijkstra(start, 0, graph.vertexs[start].connections, {}, {node: None for node in graphList}, end)
cost = result[end]
path = " ".join([str(arrInt) for arrInt in list(result.keys())])
print(path, "costing", cost)

通过这样做，输出变为

Shortest possible path from node 1 to 0: 1 6 2 0 costing 15