Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例

下面是详细讲解“Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例”的完整攻略,包括算法原理、Python实现和两个示例说明。

算法原理

Dijkstra算法是一种用于查找图中最短路径的算法。其主要思想是从起点开始,逐步扩展到其他节点,直到到达终点。在扩展的过程中,记录每个节点的最短路径和前驱节点,最终得到起点到终点的最短路径。Dijkstra算法的实现过程如下:

  1. 初始化起点的最短路径为0,其他节点的最短路径为无穷大。
  2. 选择一个未标记的节点,计算该节点到起点的距离,并更新其邻居节点的最短路径和前驱节点。
  3. 标记该节点为已访问,重复步骤2,直到到达终点或所有节点都被标记为已访问。
  4. 根据每个节点的前驱节点,构建起点到终点的短路径。

Python实现

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

import heapq

def dijkstra(graph, start, end):
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        current_distance, current_vertex = heapq.heappop(pq)
        if current_vertex == end:
            path = []
            while current_vertex != start:
                path.append(current_vertex)
                current_vertex = previous_vertices[current_vertex]
            path.append(start)
            path.reverse()
            return path, current_distance
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_vertices[neighbor] = current_vertex
                heapq.heappush(pq, (distance, neighbor))
    return None

上述代码中使用Python实现了Dijkstra算法。首先定义了一个函数dijkstra,该函数接受一个图、起点和终点作为参数,返回起点到终点的最短路径和距离。在函数中,使用堆化的方式实现了Dijkstra算法。

示例说明

以下两个示例,说明如何使用上述代码进行最短路径查找。

示例1

使用Dijkstra算法查找一个简单图的最短路径。

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

previous_vertices = {}
start = 'A'
end = 'D'
path, distance = dijkstra(graph, start, end)
print(f"最短路径为:{path},距离为:{distance}")

运行上述,输出结果为“最短路径为:['A', 'B', 'C', 'D'],距离为:4”。

上述代码中,使用Dijkstra算法查找一个简单图的最短路径。首先定义了一个图,起点和终点,并调用dijkstra函数计算最短路径和距离,最后输出结果。

示例2

使用Dijkstra算法查找一个复杂图的最短路径。

graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1, 'D': 4},
    'C': {'A': 3, 'B': 1, 'D':2, 'E': 3},
    'D': {'B': 4, 'C': 2, 'E': 1, 'F': 3},
    'E': {'C': 3, 'D': 1, 'F': 1},
    'F': {'D': 3, 'E': 1}
}

previous_vertices = {}
start = 'A'
end = 'F'
path, distance =jkstra(graph, start, end)
print(f"最短路径为:{path},距离为:{distance}")

运行上述代码,输出结果为“最短路径为:['A', 'B', 'D', 'F'],距离为:9”。

上述代码中,使用Dijkstra算法查找一个复杂图的最短路径。首先定义了一个图,起点和终点,并调用dijkstra函数计算最短路径和距离,最后输出结果。

结语

本文介绍了如何使用Python实现Dijkstra算法进行图的最短路径查找,包括算法原理、Python实现和两个示例说明。Dijkstra算法是一种用于查找图中最短路径的算法,其主要思想是从起点开始,逐步扩展到其他节点,直到到达终点。在实现中,需要注意选择适当的数据结构,并根据具体情况调整。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例 - Python技术站

(0)
上一篇 2023年5月14日
下一篇 2023年5月14日

相关文章

  • Python如何输出整数

    Python如何输出整数 在 Python 中,我们可以使用 print() 函数来输出整数。 直接输出整数 要输出整数,只需在 print() 函数中输入整数即可,例如: print(123) 这将会在屏幕输出 123。 格式化输出整数 我们也可以使用字符串格式化方法来输出整数。为了输出整数,我们使用 %d 占位符,% 符号后面跟上我们想要输出的整数,例如…

    python 2023年6月5日
    00
  • Python基于有道实现英汉字典功能

    下面我将详细讲解基于有道实现英汉字典功能的完整攻略,包括以下五个步骤。 第一步:获取API Key 1.首先访问有道翻译平台官网,注册成功后登录到官网 https://ai.youdao.com/ 2.在左侧边栏“产品服务”中找到“自然语言翻译”,并进入该页面。 3.点击“接入指南”,按提示申请API Key,申请后会获得自己的应用ID以及应用密钥。 第二步…

    python 2023年5月13日
    00
  • Python运行的17个时新手常见错误小结

    Python运行的17个时新手常见错误小结 在Python编程过程中,新手常常会遇到一些常见的错误。这些错误可能会导致程序无法正常运行,甚至会导致程序崩溃。本文将介绍Python运行的17个时新手常见错误,并提供一些示例说明。 1. 语法错误 语法错误是最常见的错误之一。它通常是由于代码中的拼写错误、少括号或引号等语法错误导致的。例如,下面的代码中缺少了一个…

    python 2023年5月13日
    00
  • Python解析、提取url关键字的实例详解

    Python解析、提取url关键字的实例详解 在Python编程中,有许多函数能够帮助我们处理与URL相关的工作。在这里,我们将介绍一些常用的函数,以及如何使用它们来提取URL以及相关的关键字。 实现步骤 导入所需模块: 可以使用urllib.request模块中的urlopen函数读取网页内容,然后使用 BeautifulSoup 进行解析。在 Pytho…

    python 2023年5月20日
    00
  • Python整数对象实现原理详解

    请看下面的详细讲解。 Python整数对象实现原理详解 什么是Python整数对象? 在Python中,整数是最基本的数据类型之一,它用来表示整数值。Python整数对象是指在Python中用来存储整数值的对象。在Python中,整数对象是不可变的,即一旦创建了一个整数对象,就不能在原地修改它的值。 Python整数对象的实现原理 在Python中,整数对象…

    python 2023年5月19日
    00
  • 详解Python中键盘鼠标的相关操作

    详解Python中键盘鼠标的相关操作 Python提供了丰富的第三方库,用于控制键盘和鼠标的操作。这些库通常被称为“GUI测试工具”(GUI Testing Tools),可以用于自动化测试、模拟用户操作、脚本自动化等场景。下面将介绍两个用于控制键盘和鼠标操作的Python库。 PyAutoGUI PyAutoGUI是一个纯Python的GUI自动化工具,可…

    python 2023年5月13日
    00
  • python正则表达式用法超详细讲解大全

    Python正则表达式用法超详细讲解大全 正则表达式是一种强大的文本处理工具,可以用于匹配、查找、替换和割字符串。Python提供了re模块来处理正则表式,本文将为您细讲解Python正则表达式语法、re模块的常用方法和两个示例说明。 正则表式的语法 在正则表达式中,使用[]表示字符集,^表示取反,-表示范围,+表示匹配或多个字符,*表示匹个或多个字符,?表…

    python 2023年5月14日
    00
  • VLC – 通过 windows/python 上的命令行以交互方式终止流/转码/windows 上的编程视频捕获

    【问题标题】:VLC – terminate stream/transcoding interactively via command line on windows/ python / programmatic video capture on windowsVLC – 通过 windows/python 上的命令行以交互方式终止流/转码/windows …

    Python开发 2023年4月6日
    00
合作推广
合作推广
分享本页
返回顶部