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通过线程实现定时器timer的方法

    Python通过线程实现定时器Timer的方法可以采用Python标准库中的threading模块,通过继承threading.Thread类并重写run()方法,实现定时器功能。 具体步骤如下: 步骤一:引入threading模块。 import threading 步骤二:定义一个继承threading.Thread类的新类。 class TimerTh…

    python 2023年5月19日
    00
  • Python学习之迭代器详解

    Python学习之迭代器详解 在Python中,迭代器(iterator)是一个非常重要的概念,它是许多高级功能和特性的基础,并且能够通过使用迭代器,更好地实现代码的可读性和代码的简洁性。本文将详细介绍什么是迭代器,如何创建一个迭代器,以及如何使用迭代器。 什么是迭代器? 迭代器是Python中的一个对象,它能够遍历(或迭代)对象的所有元素,而不需要事先知道…

    python 2023年5月14日
    00
  • Python 变量类型实例详解

    Python 变量类型实例详解 Python 是一种动态类型语言,它会在运行过程中自动确定变量的类型。Python 中的变量类型包括数字、字符串、列表、元组、集合和字典。本文将详细介绍 Python 中的变量类型,并给出一些实例说明。 数字类型 Python 中的数字类型包括整数、浮点数和复数。下面是一些数字类型的实例: 整数类型 整数是 Python 中最…

    python 2023年5月14日
    00
  • Python实现将Excel转换成xml的方法示例

    下面就为您详细讲解“Python实现将Excel转换成xml的方法示例”的完整实例教程,包含以下步骤: 环境准备 读取Excel中的数据 将数据转换为xml 将xml保存到文件中 接下来我们逐步分步讲解: 环境准备 在进行Excel转换成xml的操作之前,我们需要安装openpyxl库。这个库可以让我们读取Excel文件中的数据,同时也可以将数据转换成xml…

    python 2023年5月13日
    00
  • C++基础概念讲述

    C++基础概念讲述 数据类型 C++ 中包含了基本数据类型,例如整数和浮点数。某些情况下,我们需要更加复杂的数据类型,例如字符串和数组。以下是一些基本的数据类型: int // 整数型数据类型 float // 单精度浮点数类型 double // 双精度浮点数类型 char // 字符型数据类型 bool // 布尔型数据类型 变量 C++ 中,变量是指一…

    python 2023年5月14日
    00
  • 用Python获取智慧校园每日课表并自动发送至邮箱

    下面就是“用Python获取智慧校园每日课表并自动发送至邮箱”的完整攻略: 确定获取课表的方式 首先,需要确定获取智慧校园每日课表的方式。一般情况下,智慧校园会提供网页和移动端两个平台供学生查看课表。因此,可以选择使用Python中的网络爬虫技术来获取网页端的课表信息,或者使用微信API Library对移动端的课表信息进行爬取。 编写Python代码 下一…

    python 2023年5月19日
    00
  • 使用参数、关键字参数、*args、**kwargs 与 Python 函数混淆

    【问题标题】:Confusion with Python functions using an argument, keyword argument, *args, **kwargs使用参数、关键字参数、*args、**kwargs 与 Python 函数混淆 【发布时间】:2023-04-06 19:00:01 【问题描述】: 鉴于以下函数和对print_…

    Python开发 2023年4月7日
    00
  • 多版本Python共存的配置方法

    下面是“多版本Python共存的配置方法”的完整攻略。 一、了解Python环境 在多版本Python共存的配置之前,首先需要了解Python环境。 Python官方网站提供了不同版本的Python下载链接,例如目前官网支持的Python版本为2.7.x和3.9.x,其中2.7.x系列是Python2版本,3.9.x系列是Python3版本。同时,Pytho…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部