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] = costclass 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)但我认为输出似乎有问题。如果我想从节点 1 移动到节点 0，当前的输出是：从节点 1 到节点 0 的 DFS 遍历路径： 1 6 2 0 从节点 1 到节点 0 的 BFS 遍历路径： 1 6 2 3 0 3 4 5 从节点 1 到 0 的最短可能路径： 1 0 3 4 5 6 2 costing 10但是，我认为输出应该是：从节点 1 到节点 0 的 DFS 遍历路径： 1 6 2 0 4 5 3 从节点 1 到节点 0 的 BFS 遍历路径： 1 6 2 3 0 4 5 从节点 1 到节点 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)

通过这样做，输出变为

从节点 1 到 0 的最短路径： 1 6 2 0 成本 15