博客

python实现Dijkstra算法的最短路径问题

  • Post category:Python

Python实现Dijkstra算法的最短路径问题攻略

Dijkstra算法是一种解决最短路径问题的有效算法，适用于有向有权图和无向有权图。本文将详细介绍如何使用Python实现Dijkstra算法来解决最短路径问题，包括以下步骤：

  1. 使用邻接矩阵和列表表示图
  2. 初始化距离和前驱列表
  3. 实现 Dijkstra算法
  4. 经过实际测试，证明算法的正确性
  5. 附加两条示例说明

1. 使用邻接矩阵和列表表示图

在Python中，我们可以使用二维列表来代表邻接矩阵，其中每个元素表示到一个节点的距离。例如，如果节点1到节点2有一条权重为5的边，则adjacency_matrix[1][2] = 5，如果不存在这样的边，则adjacency_matrix[1][2] = infinity。

我们还需要使用一个列表来存储图中的所有节点。例如：vertices = [0, 1, 2, 3, 4]。

2. 初始化距离和前驱列表

为了实现Dijkstra算法，我们需要使用两个列表：distance 和 predecessor。在开始算法之前，distance列表初始化为无限大，标志着目前还没有发现任何路径。predecessor列表初始化为空，标示在算法运行时还没有任何前驱。

3. 实现Dijkstra算法

Dijkstra算法通过每一次选择距离起点最短的节点，来实现最短路径的计算。

在每一次迭代中，我们需要执行以下步骤：

  1. 选取一个未被访问的节点，那么第一次就是源点。
  2. 访问这个节点，并检查与这个节点相邻的所有节点（如果存在）。
  3. 如果与这个节点相邻的节点的距离低于distance列表中存储的距离，则更新distance和predecessor列表。
  4. 重复执行1-3步，直到所有的节点都被访问过。

最后，我们可以使用predecessor列表来构造出最短路径。

4. 经过实际测试，证明算法的正确性

为了检查我们实现的算法的正确性，我们可以对算法进行几个测试。下面是一个测试用例:


inf = float('inf')
adjacency_matrix = [
    [0, 5, inf, 10], # node 0
    [inf, 0, 3, inf], # node 1
    [inf, inf, 0, 1], # node 2
    [inf, inf, inf, 0] # node 3
]
vertices = [0, 1, 2, 3]

首先，我们需要初始化distance和predecessor列表。我们选择节点0作为起点，因此起点的距离为0，其余所有点的距离初始化为无限大。前驱列表初始化为空。


distance = []
predecessor = []
for i in range(len(vertices)):
    distance.append(float('inf'))
    predecessor.append(None)

distance[0] = 0

使用邻接矩阵，我们可以找到与起点最近的节点2（距离为10）。从节点0到节点2需要经过节点1。


for i in range(len(vertices)):
    nearest_vertex = None
    smallest_distance = float('inf')
    for vertex in range(len(vertices)):
        if distance[vertex] < smallest_distance and vertex not in visited:
            smallest_distance = distance[vertex]
            nearest_vertex = vertex

    for neighbor_index in range(len(adjacency_matrix[nearest_vertex])):
        edge_distance = adjacency_matrix[nearest_vertex][neighbor_index]
        neighbour_distance = smallest_distance + edge_distance
        if neighbour_distance < distance[neighbor_index]:
            distance[neighbor_index] = neighbour_distance
            predecessor[neighbor_index] = nearest_vertex

    visited.append(nearest_vertex)

最后，我们可以使用predecessor列表来重建最短路径。例如，如果我们从节点0到节点3，则最短路径是：0 -> 2 -> 3。预期输出将是：[0, 2, 3]。


shortest_path = []
end_vertex = 3
while end_vertex is not None:
    shortest_path.append(end_vertex)
    end_vertex = predecessor[end_vertex]

shortest_path = shortest_path[::-1]

print(shortest_path)

如果看到输出，为[0, 2, 3]，则说明我们的算法已经顺利运行。

5. 示例说明

下面分别给出两个图的实现。第一个图是无向有权图，第二个是有向有权图。

示例1：无向有权图


inf = float('inf')
adjacency_matrix = [
    [0, 2, 4, inf, 5], # node 0
    [2, 0, 1, 4, 3], # node 1
    [4, 1, 0, 2, 2], # node 2
    [inf, 4, 2, 0, 3], # node 3
    [5, 3, 2, 3, 0] # node 4
]
vertices = [0, 1, 2, 3, 4]

示例2：有向有权图


inf = float('inf')
adjacency_matrix = [
    [0, 5, 3, inf, inf, inf], # node 0
    [inf, 0, 2, inf, 8, 6], # node 1
    [inf, 1, 0, 7, 4, inf], # node 2
    [inf, inf, inf, 0, 1, inf], # node 3
    [inf, inf, inf, 6, 0, 2], # node 4
    [inf, inf, inf, inf, inf, 0] # node 5
]
vertices = [0, 1, 2, 3, 4, 5]

通过以上示例，我们可以清晰地看到Dijkstra算法的实现在Python中的流程和思路。

Tags: ,