python矩阵/字典实现最短路径算法

Python中实现最短路径算法可以使用矩阵和字典两种方式，下面将逐一详细讲解这两种实现方式。

使用矩阵实现最短路径算法

简介

矩阵是将图中各个节点之间的距离存储下来的方式，通常使用二维数组来实现。我们将从以下几个方面来讲解使用矩阵实现最短路径算法：

1. 如何初始化一个矩阵；
2. 如何使用矩阵实现Dijkstra算法；
3. 如何输出最短路径。

1. 初始化矩阵

假设我们有一张如下所示的有向带权图，图中共有5个节点(A、B、C、D、E)，每个节点之间都有相应的距离：

     5      -3
(0)--->(1)<----(2)
 |         \     |
 |          \   -2
10           \  |
 |            V V
 V            (3)
(4)---------->(5)
     1

我们可以使用一个二维数组，来将节点之间的距离存储下来（使用inf表示不可达）：

INF = float("inf")
graph = [
    [0, 5, INF, 10, INF, INF],
    [INF, 0, 3, INF, INF, INF],
    [INF, INF, 0, -2, INF, INF],
    [INF, INF, INF, 0, 6, INF],
    [INF, INF, INF, INF, 0, 1],
    [INF, INF, INF, INF, INF, 0]
]

2. 使用矩阵实现Dijkstra算法

Dijkstra算法是一个经典的图论算法，可以用来求解单源最短路径。使用矩阵实现Dijkstra算法，需要用到以下数据结构：

• 距离列表dist：存储每个节点到起点的最短距离；
• 判断列表sptSet：用于判断节点是否已被遍历；
• 节点数量V：存储节点个数。

下面是使用矩阵实现Dijkstra算法的Python代码：

def dijkstra(graph, src):
    V = len(graph)
    dist = [INF] * V
    sptSet = [False] * V
    dist[src] = 0
    for _ in range(V):
        u = minDistance(dist, sptSet)
        sptSet[u] = True
        for v in range(V):
            if graph[u][v] and not sptSet[v] and dist[u] != INF and dist[u] + graph[u][v] < dist[v]:
                dist[v] = dist[u] + graph[u][v]
    return dist

def minDistance(dist, sptSet):
    min_dist = INF
    min_index = -1
    for v in range(len(dist)):
        if not sptSet[v] and dist[v] < min_dist:
            min_dist = dist[v]
            min_index = v
    return min_index

3. 输出最短路径

在Dijkstra算法完成之后，我们可以使用以下代码来输出起点到其他节点的最短路径：

for node in range(V):
    print(f"最短路径({src} -> {node}): {dijkstra(graph, src)[node]}")

其中，graph是存储节点距离的矩阵，src是起点节点的编号，node是需要输出最短路径的节点编号。

使用字典实现最短路径算法

简介

与矩阵相比，字典可以更加灵活的存储图结构，适用于处理不规则的图形结构。我们将从以下几个方面来讲解使用字典实现最短路径算法：

1. 如何初始化一个字典；
2. 如何使用字典实现Dijkstra算法。

1. 初始化字典

使用字典实现最短路径算法，我们需要使用两个字典来存储节点与其邻居节点及其对应的距离，一个字典用于存储起点到其他节点的最短路径。以下是一个示例字典：

graph = {
  "A": {"B": 5, "D": 10},
  "B": {"C": 3},
  "C": {"D": -2, "F": 1},
  "D": {"C": 6, "E": -3},
  "E": {"F": 1},
  "F": {}
}

start = "A"

2. 使用字典实现Dijkstra算法

与使用矩阵实现Dijkstra算法相比，使用字典实现Dijkstra算法需要对数据结构做出一些调整。下面是使用字典实现Dijkstra算法的Python代码：

def dijkstra(graph, start):
    shortest_paths = {start: 0}
    current_node = start
    visited = set()
    while current_node is not None:
        visited.add(current_node)
        destinations, weight = graph[current_node].items()
        for next_node, distance in destinations.items():
            if next_node in visited:
                continue
            new_distance = shortest_paths[current_node] + distance
            if next_node not in shortest_paths or new_distance < shortest_paths[next_node]:
                shortest_paths[next_node] = new_distance
        current_node = None
        for node in graph:
            if node not in visited and node in shortest_paths:
                if current_node is None or shortest_paths[node] < shortest_paths[current_node]:
                    current_node = node
    return shortest_paths

在上面的代码中，我们首先从起点开始，维护一个包含起点的最短路径字典shortest_paths。之后，遍历起点的邻居节点，更新字典中关于这些邻居节点的最短距离。接着，在未被遍历的节点中选择距离最短的一个节点，更新当前节点，直到所有的节点都被遍历。

以上是使用矩阵和字典两种方法实现最短路径算法的详细攻略。明白了吗？