下面是详细讲解“Python实现Dijkstra静态寻路算法”的完整攻略,包括算法原理、Python实现和两个示例说明。
算法原理
Dijkstra算法是一种用于寻找带权图中单源最短路径的算法,其基本思想是从起点开始,逐步扩展到其他节点,直到到达终点。具体步骤如下:
- 初始化起点到其他节点的距离为无穷大,起点到自身的距离为0;
- 选取距离起点最近的节点将其加入已访问节点集合;
- 更新起点到其他节点的距离,如果经过当前节点到达其他节点的距离更短,则更新距离;
- 重复步骤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技术站