Python Dijkstra算法是什么

舞夢輝影

发布： 2025-10-11 10:05:01

原创

424人浏览过

Dijkstra算法用于求带权图单源最短路径，核心是贪心策略，每步选最近未处理节点并更新邻居距离。Python常用字典建图、heapq优化，初始化起点距离为0，其余无穷大，用优先队列存（距离, 节点），依次出队最小距离节点，遍历邻居松弛距离，直到队列为空。示例中从A出发得最短路径：{'A': 0, 'B': 1, 'C': 3, 'D': 4}。适用于无向或有向图，要求边权非负，不适用负权边，常见于路由、导航等场景，理解松弛和优先队列是关键。

python dijkstra算法是什么

Dijkstra算法是一种用于求解带权图中单源最短路径的经典算法，由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）在1956年提出。在Python中实现Dijkstra算法，通常是为了找出从一个起始节点到图中其他所有节点的最短路径。

核心思想：贪心策略

Dijkstra算法采用贪心策略，每一步都选择当前距离起点最近且未被处理的节点，然后更新其邻居的距离。这个过程持续进行，直到所有可达节点都被处理完毕。

它适用于有向图或无向图，但要求所有边的权重为非负数（即不能有负权边）。

Python中的常见实现方式

在Python中，通常使用字典表示图，用优先队列（heapq）优化查找最小距离节点的过程，从而提高效率。

立即学习“Python免费学习笔记（深入）”；

基本步骤如下：

初始化起点距离为0，其他节点距离为无穷大（float('inf')）
使用优先队列存储（距离, 节点）对，按距离从小到大排序
每次取出距离最小的节点，遍历其邻居并尝试松弛（relax）距离
重复直到队列为空

简单示例代码

import heapq
<p>def dijkstra(graph, start):</p>
                    <div class="aritcle_card">
                        <a class="aritcle_card_img" href="/ai/%E7%AE%97%E5%AE%B6%E4%BA%91">
                            <img src="https://img.php.cn/upload/ai_manual/000/000/000/175679969239968.png" alt="算家云">
                        </a>
                        <div class="aritcle_card_info">
                            <a href="/ai/%E7%AE%97%E5%AE%B6%E4%BA%91">算家云</a>
                            <p>高效、便捷的人工智能算力服务平台</p>
                            <div class="">
                                <img src="/static/images/card_xiazai.png" alt="算家云">
                                <span>37</span>
                            </div>
                        </div>
                        <a href="/ai/%E7%AE%97%E5%AE%B6%E4%BA%91" class="aritcle_card_btn">
                            <span>查看详情</span>
                            <img src="/static/images/cardxiayige-3.png" alt="算家云">
                        </a>
                    </div>
                <h1>初始化距离表</h1><pre class='brush:python;toolbar:false;'>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

登录后复制