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)

但我认为输出似乎有问题。如果我想从节点 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

您的代码实际上存在几个问题：您需要指定您的 Djikstra 算法在哪里停止，在您的代码中没有提到什么是结束节点（在您的示例中它应该是 0）计算成本并cost = result[len(result) - 1]不能获得字典中的最后一个元素（字典通常没有排序，因此“最后一个元素”甚至不存在！）。您应该将成本检索为cost = result[end]，其中end是最终节点，在您的示例中为 0。您将该函数调用为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 = 1end = 0result = 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