python实现Dijkstra算法

Dijkstra算法是一种用于计算图中单源最短路径的经典算法。在Python中，你可以使用优先队列堆）来实现Dijkstra算法。下面是一个使用优先队列实现Dijkstra算法的示例代码：

import heapq

class Node:
    def __init__(self, name):
        self.name = name
        self.neighbors = []
        self.distance = float('inf')
        self.visited = False
        self.predecessor = None

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

def dijkstra(start_node):
    start_node.distance = 0
    heap = [start_node]

    while heap:
        current_node = heapq.heappop(heap)
        current_node.visited = True

        for neighbor in current_node.neighbors:
            if not neighbor.visited:
                new_distance = current_node.distance + neighbor.distance
                if new_distance < neighbor.distance:
                    neighbor.distance = new_distance
                    neighbor.predecessor = current_node
                    heapq.heappush(heap, neighbor)

def get_shortest_path(end_node):
    node = end_node
    shortest_path = []

    while node is not None:
        shortest_path.insert(0, node.name)
        node = node.predecessor

    return shortest_path

# 创建节点和边
nodeA = Node("A")
nodeB = Node("B")
nodeC = Node("C")
nodeD = Node("D")
nodeE = Node("E")

nodeA.neighbors.append(nodeB)
nodeA.neighbors.append(nodeC)
nodeB.neighbors.append(nodeD)
nodeB.neighbors.append(nodeC)
nodeC.neighbors.append(nodeD)
nodeD.neighbors.append(nodeE)

nodeA.distance = 0

# 执行Dijkstra算法
dijkstra(nodeA)

# 获取最短路径
end_node = nodeE
shortest_path = get_shortest_path(end_node)
print("最短路径:", shortest_path)
print("最短距离:", end_node.distance)

在上述代码中，我们首先定义了一个 `Node` 类，表示图中的节点。每个节点有一个名称 `name`，一个邻居节点列表 `neighbors`，一个距离值 `distance`，一个访问标志 `visited` 和一个前驱节点 `predecessor`。我们还重载了 `<` 运算符，以便通过节点的距离值进行比较。

然后，我们定义了 `dijkstra` 函数来执行Dijkstra算法。该函数以起始节点作为参数，并使用优先队列（堆）来存储待访问的节点。在算法的每一步中，我们从堆中取出距离值最小的节点，将其标记为已访问，并更新其邻居节点的距离和前驱节点。

最后，我们定义了 `get_shortest_path` 函数来获取从起始节点到给定节点的最短路径。该函数从给定节点开始，沿着前驱节点一直回溯到起始节点，并将节点名称添加到最短路径列表中。

在示例中，我们创建了一个简单的图，并将起始节点设置为节点A。然后，我们执行Dijkstra算法，并获取从起始节点到节点E的最短路径和最短距离。

希望这个示例能够帮助你理解如何在Python中实现Dijkstra算法！如果你还有其他问题，请随时提问。