博客

python实现Dijkstra静态寻路算法

  • Post category:Python

下面是详细讲解“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表示添加边的方法，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算法是一种用于寻找带权图中单源最短路径的算法，其基本思想是从起点开始，逐步扩展到其他节点，直到到达终点。在实际应用中，需要注意选取合适的数据结构和算法实现，以获得更好的寻路效。

Tags: ,