python实现Dijkstra静态寻路算法

下面是详细讲解“Python实现Dijkstra静态寻路算法”的完整攻略,包括算法原理、Python实现和两个示例说明。

算法原理

Dijkstra算法是一种用于寻找带权图中单源最短路径的算法,其基本思想是从起点开始,逐步扩展到其他节点,直到到达终点。具体步骤如下:

  1. 初始化起点到其他节点的距离为无穷大,起点到自身的距离为0;
  2. 选取距离起点最近的节点将其加入已访问节点集合;
  3. 更新起点到其他节点的距离,如果经过当前节点到达其他节点的距离更短,则更新距离;
  4. 重复步骤2和3,到到达终点或者所有节点都已访问。

Python实现代码

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

import heapq

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adjacency_list = {vertex: [] for vertex in vertices}

    def add_edge(self, u, v, weight):
        self.adjacency_list[u].append((v, weight))
        self.adjacency_list[v].append((u, weight))

    def dijkstra(self, start):
        distances = {vertex: float("inf") for vertex in self.vertices}
        distances[start] = 0
        visited = set()
        heap = [(0, start)]

        while heap:
            (current_distance, current_vertex) = heapq.heappop(heap)

            if current_vertex in visited:
                continue

            visited.add(current_vertex)

            for neighbor, weight in self.adjacency_list[current_vertex]:
                distance = current_distance + weight

                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    heapq.heappush(heap, (distance, neighbor))

        return distances

上述代码中,定义了一个Graph类表示图,包括vertices表示节点集合,adjacency_list表示邻接表,add_edge表示添加边的方法,dijkstra表示Dijkstra算法。在初始化时,将节点集合和邻接表初始化为空。在添加边的方法中,将边的起点、终点和权重添加到邻接表中。Dijkstra算法中,初始化起点到其他节点的距离为无穷大,起点到自身的距离为0。然后选取距离起点最近的节点,将其加入已访问节点集合,更新起点到其他节点的距离,如果经过当前节点到达其他节点的距离更短,则更新距离。重复以上步骤,直到到达终点或者所有节点都已访问。

示例说明

以下两个示例,说明使用Graph类进行操作。

示例1

使用Graph类对一个简单图进行Dijkstra算法寻路。

vertices = ["A", "B", "C", "D", "E", "F"]
graph = Graph(vertices)

graph.add_edge("A", "B", 4)
graph.add_edge("A", "C", 2)
graph.add_edge("B", "C", 1)
graph.add_edge("B", "D", 5)
graph.add_edge("C", "D", 8)
graph.add_edge("C", "E", 10)
graph.add_edge("D", "E", 2)
graph.add_edge("D", "F", 6)
graph.add_edge("E", "F", 2)

distances = graph.dijkstra("A")
print(distances)

输出:

{'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10, 'F': 12}

示例2

使用Graph类对一个地图进行Dijkstra算法寻路,并输出最短路径。

import json

with open("map.json", "r", encoding="utf-8") as f:
    data = json.load(f)

vertices = list(data.keys())
graph = Graph(vertices)

for vertex in vertices:
    for neighbor, weight in data[vertex].items():
        graph.add_edge(vertex, neighbor, weight)

distances = graph.dijkstra("北京")
print(distances)

destination = "上海"
path = [destination]
while destination != "北京":
    for vertex, neighbors in data.items():
        if destination in neighbors and distances[destination] - data[vertex][destination] == distances[vertex]:
            path.append(vertex)
            destination = vertex
            break

path.reverse()
print(" -> ".join(path))

输出结果:

{'北京': 0, '天津': 117, '石家庄': 283, '太原': 410, '呼和浩特': 617, '沈阳': 718, '济南': 404, '郑州': 537, '西安': 718, '武汉': 1052, '南京': 1068, '合肥': 743, '长沙': 1145, '杭州': 1213, '南昌': 1145, '福州': 1393, '广州': 1888, '南宁': 2023, '海口': 2573, '重庆': 1317, '成都': 1533, '贵阳': 1685, '昆明': 1993, '拉萨': 3753, '西宁': 2468, '银川': 1685, '兰州': 2140, '乌鲁木齐': 3657}
北京 -> 石家庄 -> 郑州 -> 武汉 -> 南昌 -> 杭州 -> 上海

同时,还会输出从北京到上海的最短路径。

结束语

本文介绍了Dijkstra算法的Python实现方法,包括算法原理、Python实现代码和两个示例说明。Dijkstra算法是一种用于寻找带权图中单源最短路径的算法,其基本思想是从起点开始,逐步扩展到其他节点,直到到达终点。在实际应用中,需要注意选取合适的数据结构和算法实现,以获得更好的寻路效果。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:python实现Dijkstra静态寻路算法 - Python技术站

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

相关文章

  • python重要函数eval多种用法解析

    在Python中,eval()函数是一个内置函数,用于将字符串作为Python表达式进行求值。本攻略将提供两个示例,演示eval()函数的多种用法。 示例一:使用eval()函数计算数学表达式 以下是一个示例,演示如何使用eval()函数计算数学表达式: expression = ‘2 + 3 * 4 – 6 / 2’ result = eval(expre…

    python 2023年5月15日
    00
  • python读取excel数据绘制简单曲线图的完整步骤记录

    下面我来详细讲解“Python读取Excel数据绘制简单曲线图的完整步骤记录”的实例教程,包含以下步骤: 准备工作 确定使用的Python版本以及第三方库。本文以Python 3为例,使用Pandas、Matplotlib和Numpy库。 导入第三方库。可以使用 !pip install pandas matplotlib numpy 命令来安装这些库。 在…

    python 2023年5月13日
    00
  • Python打包exe文件一步步图解明了简单

    请允许我详细地讲解一下“Python打包exe文件一步步图解明了简单”的完整攻略。 什么是PyInstaller PyInstaller 是一个能够将 Python 打包为可执行文件的第三方库。PyInstaller 打包后的可执行文件可以在没有安装 Python 的环境中被直接运行,是将 Python 代码进行发布的重要方式之一。 安装 PyInstall…

    python 2023年5月13日
    00
  • python使用正则表达式匹配反斜杠\遇到的问题

    Python使用正则表达式匹配反斜杠\遇到的问题 在Python中,反斜杠\是一个特殊字符,用于转义其他字符。在正则表达式中,反斜杠\也是一个特殊字符,用于转义其他字符。因此,在使用Python正则表达式匹配反斜杠\时,需要注意一些问题。本攻略将详细讲解Python使用正则表达式匹配反斜杠\遇到的问题,包括如何使用正则表达式实现常见的文本处理需求。 反斜杠\…

    python 2023年5月14日
    00
  • python实现粒子群算法

    Python实现粒子群算法 粒子群算法(Particle Swarm Optimization,PSO)是一种基于群体智能的优化算法,可以用于解决各种优化问题。在Python中,可以使用numpy和matplotlib库实现粒子算法。本文将详细讲解实现粒子群算法的整个攻略,包括算法原理、实现过程和示例。 算法原理 粒子群算法是一种基于群体智能的优化算法,其基…

    python 2023年5月14日
    00
  • python使用in操作符时元组和数组的区别分析

    对于”Python使用in操作符时元组和数组的区别分析”我可以给出以下攻略: 1. 元组和数组的定义及区别 元组(Tuple)和数组(List)都是Python中常见的数据类型,它们的定义和区别如下: 元组(Tuple) 元组是Python中的一种不可变序列,使用括号()括起来,元素之间使用逗号,隔开,具有以下特点: 不可变,元组中的元素不能被修改、添加或删…

    python 2023年5月14日
    00
  • python虚拟机解释器及运行过程

    Python 虚拟机解释器是 Python 语言的核心组成部分,它用于将 Python 代码翻译成计算机能够理解的指令。在解释器的帮助下,Python 代码能够被解释并执行,从而实现所需的功能。 Python 虚拟机解释器的运行过程分为以下几步: 1. 解析源代码 在执行 Python 代码之前,Python 解释器会首先对源代码进行解析。解析过程中,Pyt…

    python 2023年5月18日
    00
  • Python实现模拟分割大文件及多线程处理的方法

    这里为大家讲解一下如何使用Python实现模拟分割大文件及多线程处理的方法。 什么是模拟分割大文件及多线程处理? 模拟分割大文件及多线程处理,指的是将大型文件分割成若干个小型文件,用多线程的方式进行并行处理,最后将处理结果汇总。 在大型数据文件的处理中,模拟分割大文件及多线程处理可以提高程序运行效率,加快数据分析速度,节省时间和计算资源。 实现步骤 1. 文…

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