距离矩阵路径优化Python Dijkstra(迪杰斯特拉)算法和冲突驱动子句学习

Last updated 1 year ago

Was this helpful?

Dijkstra算法

Dijkstra 算法是一种流行的寻路算法，通常用于基于图的问题，例如在地图上查找两个城市之间的最短路径、确定送货卡车可能采取的最短路径，甚至创建游戏地图。其背后的直觉基于以下原则：从起始顶点访问所有相邻顶点，同时跟踪迄今为止距起始顶点的最小距离。该算法按以下步骤运行：

创建一个数组，用于保存每个顶点与起始顶点的距离。最初，将所有顶点的距离设置为无穷大，起始顶点除外，起始顶点应设置为 0。
创建一个优先级队列（堆）并插入距离为0的起始顶点。
当优先级队列中仍有顶点时，选择距起始顶点记录距离最小的顶点并访问其相邻顶点。
对于每个相邻顶点，检查它是否已经被访问过。如果尚未访问过，则通过将其权重添加到迄今为止为其父级找到的最小距离来计算其暂定距离
如果这个暂定距离小于之前记录的值（如果有），请在我们的“distances”数组中更新它。
最后，将这个访问过的顶点及其更新的距离添加到我们的优先级队列中，并重复步骤 3，直到我们到达目的地或耗尽所有节点。

通过迭代所有相邻节点，我们可以确保我们已经探索了每条可能的路径，以确定哪条路径的总成本（距离）最短。我们使用优先级队列数据结构来有效地跟踪接下来需要访问哪些节点，而不是在每次迭代中扫描每个节点。

通过以这种方式跟踪距离并迭代邻居，我们最终可以找到从起始节点（或更确切地说距离[源]）到图中其他节点/城市的所需最小路径。

这就是 Dijkstra 算法背后的基本直觉！通过迭代地执行这些步骤，我们最终将找出从源顶点开始的图中任意顶点的最短距离。现在让我们用 Python 编写代码。

Python实现算法

以下是如何通过示例图使用此函数：

这演示了如何将 Dijkstra 算法与 Python 结合使用来查找图中的最短路径。

Python可视化算法

开放街道地图(OSM)

Python Dijkstra算法寻找最短路径

冲突驱动子句学习

预处理：计算距离矩阵
创建网络图
使用 NetworkX 计算最短路径
使用 Plotly 动画生成模拟
使用 OR-Tools 解决旅行商问题（简单的路线优化）
使用 OR-Tools 解决车辆路径问题（高级路径优化）

源代码

Last updated 1 year ago

Was this helpful?

Dijkstra算法

创建一个数组，用于保存每个顶点与起始顶点的距离。最初，将所有顶点的距离设置为无穷大，起始顶点除外，起始顶点应设置为 0。
创建一个优先级队列（堆）并插入距离为0的起始顶点。
当优先级队列中仍有顶点时，选择距起始顶点记录距离最小的顶点并访问其相邻顶点。
对于每个相邻顶点，检查它是否已经被访问过。如果尚未访问过，则通过将其权重添加到迄今为止为其父级找到的最小距离来计算其暂定距离
如果这个暂定距离小于之前记录的值（如果有），请在我们的“distances”数组中更新它。
最后，将这个访问过的顶点及其更新的距离添加到我们的优先级队列中，并重复步骤 3，直到我们到达目的地或耗尽所有节点。

通过以这种方式跟踪距离并迭代邻居，我们最终可以找到从起始节点（或更确切地说距离[源]）到图中其他节点/城市的所需最小路径。

Python实现算法

以下是如何通过示例图使用此函数：

# 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可视化算法

开放街道地图(OSM)

Python Dijkstra算法寻找最短路径

冲突驱动子句学习

预处理：计算距离矩阵
创建网络图
使用 NetworkX 计算最短路径
使用 Plotly 动画生成模拟
使用 OR-Tools 解决旅行商问题（简单的路线优化）
使用 OR-Tools 解决车辆路径问题（高级路径优化）

源代码

def min_distance(distances, visited):
    min_val = float('inf')
    min_index = -1
    for i in range(len(distances)):
        if distances[i] < min_val and i not in visited:
            min_val = distances[i]
            min_index = i
    return min_index

def dijkstra_algorithm(graph, start_node):
    num_nodes = len(graph)
    distances = [float('inf')] * num_nodes
    visited = []
    distances[start_node] = 0
    for 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_distance
    return distances