国内最大的开源网站,自己制作头像的网站 设计 动漫,东莞高端做网站,温州网站制作优化Dijkstra算法
Dijkstra 算法是一种流行的寻路算法#xff0c;通常用于基于图的问题#xff0c;例如在地图上查找两个城市之间的最短路径、确定送货卡车可能采取的最短路径#xff0c;甚至创建游戏地图。其背后的直觉基于以下原则#xff1a;从起始顶点访问所有相邻顶点通常用于基于图的问题例如在地图上查找两个城市之间的最短路径、确定送货卡车可能采取的最短路径甚至创建游戏地图。其背后的直觉基于以下原则从起始顶点访问所有相邻顶点同时跟踪迄今为止距起始顶点的最小距离。 该算法按以下步骤运行
创建一个数组用于保存每个顶点与起始顶点的距离。最初将所有顶点的距离设置为无穷大起始顶点除外起始顶点应设置为 0。创建一个优先级队列堆并插入距离为0的起始顶点。当优先级队列中仍有顶点时选择距起始顶点记录距离最小的顶点并访问其相邻顶点。对于每个相邻顶点检查它是否已经被访问过。 如果尚未访问过则通过将其权重添加到迄今为止为其父级找到的最小距离来计算其暂定距离如果这个暂定距离小于之前记录的值如果有请在我们的“distances”数组中更新它。最后将这个访问过的顶点及其更新的距离添加到我们的优先级队列中并重复步骤 3直到我们到达目的地或耗尽所有节点。
通过迭代所有相邻节点我们可以确保我们已经探索了每条可能的路径以确定哪条路径的总成本距离最短。 我们使用优先级队列数据结构来有效地跟踪接下来需要访问哪些节点而不是在每次迭代中扫描每个节点。
通过以这种方式跟踪距离并迭代邻居我们最终可以找到从起始节点或更确切地说距离[源]到图中其他节点/城市的所需最小路径。
这就是 Dijkstra 算法背后的基本直觉通过迭代地执行这些步骤我们最终将找出从源顶点开始的图中任意顶点的最短距离。现在让我们用 Python 编写代码。
Python实现算法
def min_distance(distances, visited):min_val float(inf)min_index -1for i in range(len(distances)):if distances[i] min_val and i not in visited:min_val distances[i]min_index ireturn min_indexdef dijkstra_algorithm(graph, start_node):num_nodes len(graph)distances [float(inf)] * num_nodesvisited []distances[start_node] 0for i in range(num_nodes):current_node min_distance(distances, visited)visited.append(current_node)for j in range(num_nodes):if graph[current_node][j] ! 0:new_distance distances[current_node] graph[current_node][j]if new_distance distances[j]:distances[j] new_distancereturn distances以下是如何通过示例图使用此函数
# 2D array
graph [[0, 7, 9, 0, 0, 14],[7, 0, 10, 15, 0, 0],[9, 10, 0, 11, 0, 2],[0, 15, 11, 0, 6, 0],[0, 0, 0, 6, 0 ,9],[14. 0 ,2 ,0 ,9 ,8 ,10]]shortest_distances dijkstra_algorithm(graph, A)print(shortest_distances)[0.00... # Distance from start node to itself is zero
7
9
20
20
12
]这演示了如何将 Dijkstra 算法与 Python 结合使用来查找图中的最短路径。
Python可视化 Dijkstra算法
开放街道地图(OSM)
Python Dijkstra算法寻找最短路径
冲突驱动子句学习
预处理计算距离矩阵创建网络图使用 NetworkX 计算最短路径使用 Plotly 动画生成模拟使用 OR-Tools 解决旅行商问题简单的路线优化使用 OR-Tools 解决车辆路径问题高级路径优化
参阅一 - 亚图跨际
参阅二 - 亚图跨际
