python实现dijkstra

以下是Python实现Dijkstra算法的示例代码：

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    return distances

其中，`graph`是一个字典，表示图的邻接表，`start`是起点。函数返回一个字典，表示从起点到每个节点的最短距离。

相关问题

python实现dijkstra算法

以下是Python实现Dijkstra算法的代码：

import heapq

def dijkstra(graph, start, end):
    # 初始化距离和前驱字典
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    predecessors = {node: None for node in graph}

    # 用堆来实现优先队列
    pq = [(0, start)]
    while len(pq) > 0:
        # 取出堆顶元素
        current_distance, current_node = heapq.heappop(pq)

        # 如果当前节点已经被处理过了，就跳过
        if current_distance > distances[current_node]:
            continue

        # 遍历当前节点的邻居
        for neighbor, weight in graph[current_node].items():
            # 计算到该邻居的距离
            distance = current_distance + weight

            # 如果新的距离比之前计算的距离更短，就更新距离和前驱字典
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                predecessors[neighbor] = current_node
                heapq.heappush(pq, (distance, neighbor))

    # 返回最短路径和距离
    path = []
    current_node = end
    while current_node is not None:
        path.insert(0, current_node)
        current_node = predecessors[current_node]

    return path, distances[end]

该函数接受一个字典类型的图，起点和终点作为输入，返回最短路径和距离。其中，图的格式为{节点1: {邻居1: 权重1, 邻居2: 权重2, ...}, 节点2: {...}, ...}。该函数使用堆来实现优先队列，以提高效率。

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算法！如果你还有其他问题，请随时提问。