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实现目录树生成示例

    当我们需要查看一个文件夹下的文件或者文件夹时,常常需要使用到目录树。Python提供了一些库可以生成目录树,其中最常用的是os库和os.walk()方法,通过这些方式可以轻松生成目录树。 下面是一个简单的示例,展示如何使用Python实现目录树的打印输出。 示例一: import os def print_directory_contents(path): …

    python 2023年5月20日
    00
  • python实现 获取b站主播直播间 粉丝牌信息的方法

    下面是“python实现获取B站主播直播间粉丝牌信息的方法”的完整攻略。 简介 Bilibili(B站)是一家国内知名的视频分享平台,网站内有许多知名的up主,这些up主通过直播和上传视频吸引了大量的粉丝。直播间粉丝牌是B站直播间的一种特殊礼物,拥有这种礼物的用户可以在直播间内展示出自己的特殊身份。本文将介绍如何使用Python获取B站主播直播间粉丝牌的信息…

    python 2023年6月3日
    00
  • python实现高效的遗传算法

    下面是详细讲解“Python实现高效的遗传算法”的完整攻略,包括算法原理、Python实现和两个示例说明。 算法原理 遗传算法是一种基于生物进化原理的优化算法,其基本思想是通过模拟自然选择、交叉和变异等过程,不断优化种群中的个体,从而得到最优解。具体步骤如下: 初始化种群,随机生成一组个体; 计算每个个体的适应度,即目标函数的值; 选择优秀的个体,为下一代的…

    python 2023年5月14日
    00
  • 布同 统计英文单词的个数的python代码

    下面是详细讲解“统计英文单词个数的python代码”的攻略。 1. 准备工作 首先我们需要安装Python,可以去官网下载并安装。 接着,需要在文本编辑器中打开一个文本文件,输入一些英文文本,保存到本地。 2. 代码实现 以下是Python代码实现英文单词个数统计的方法: import re def count_words(text): # 过滤掉非英文字符…

    python 2023年6月5日
    00
  • python retrying模块的使用方法详解

    Python retrying模块的使用方法详解 在Python编程中,我们经常需要处理一些不稳定的操作,例如网络请求、文件读写等。这些操作可能会因为网络波动服务器故障等原因而失败,因此我们需要对这些操作进行重试。Python retrying模块就是为了解决这个问题而设计。 安装 在使用Python retrying模块之前,我们需要先安装它。可以使用pi…

    python 2023年5月13日
    00
  • Python的函数使用介绍

    让我们开始介绍“Python的函数使用”。 函数的概念 函数是一段可重用的代码块,其可以接收参数、进行处理、并返回一个结果。这种可重用性使得代码更加模块化、可读性更高,且方便调用。Python中的函数使用起来非常方便、灵活,因此在Python开发中函数是非常重要的概念。 函数的定义与调用 Python中定义函数非常简单,在函数名后加括号即可,如下所示: de…

    python 2023年5月31日
    00
  • 如何在 Redis 中实现时间序列数据存储?

    以下是详细讲解如何在 Redis 中实现时间序列数据存储的完整使用攻略。 Redis 时间序列数据存储简介 Redis 时间序列数据存储是一常用的数据存储技术,可以用于储序列数据,如股票价格、气象数据、传感器数据等。Redis 时间序列存储的特点如下: Redis 时间序列数据储是基于 Redis 的数据结构实现。 Redis 时间序列数据存储可以通过过期时…

    python 2023年5月12日
    00
  • python+matplotlib实现动态绘制图片实例代码(交互式绘图)

    下面将为你详细介绍Python+Matplotlib实现动态绘制图片的完整攻略。首先,我们需要掌握以下基本知识: Matplotlib简介 Matplotlib是一个Python的绘图库,它可以生成各种静态图表、交互式图表和动态图表。Matplotlib提供了一套完整的绘图工具,并支持公认的第三方工具包,比如Seaborn、ggplot等,同时它也提供了方便…

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