四种求图的最短路径模板

**四种求图的最短路径模板**

在计算机科学中，求图的最短路径是指从一个顶点到另一个顶点的最短路径。这种问题在许多领域都有应用，如网络规划、交通流预测等。在本文中，我们将介绍四种常见的求图的最短路径模板：Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法和A*算法。

###1. Dijkstra算法Dijkstra算法是最早的一种求图的最短路径算法，于1959年由Edsger W. Dijkstra提出。该算法适用于有向图或无向图，并且每个顶点都有一个权值。

**模板代码**

import heapqdef dijkstra(graph, start):
 # 初始化距离和前驱节点表 distances = {node: float('inf') for node in graph}
 distances[start] =0 predecessors = {start: None}

 # 构造优先队列 queue = [(0, start)]

 while queue:
 current_distance, current_node = heapq.heappop(queue)

 # 如果当前距离大于已知最短距离，则跳过 if current_distance > distances[current_node]:
 continue for neighbor, weight in graph[current_node].items():
 distance = current_distance + weight # 如果新距离小于已知最短距离，则更新 if distance < distances[neighbor]:
 distances[neighbor] = distance predecessors[neighbor] = current_node heapq.heappush(queue, (distance, neighbor))

 return distances, predecessors

**注释**

* `graph`是图的邻接表，表示每个顶点的相邻节点和权值。
* `start`是起始顶点。
* `distances`是距离表，记录从起始顶点到其他顶点的最短距离。
* `predecessors`是前驱节点表，记录从起始顶点到其他顶点的前驱节点。

###2. Bellman-Ford算法Bellman-Ford算法是Dijkstra算法的一个扩展版本，可以处理负权值和循环图。该算法适用于有向图或无向图，并且每个顶点都有一个权值。

**模板代码**

def bellman_ford(graph, start):
 # 初始化距离表 distances = {node: float('inf') for node in graph}
 distances[start] =0 # 构造前驱节点表 predecessors = {start: None}

 # Relax edges V-1 次 for _ in range(len(graph) -1):
 for u, v in graph.items():
 for neighbor, weight in v.items():
 distance = distances[u] + weight # 如果新距离小于已知最短距离，则更新 if distance < distances[neighbor]:
 distances[neighbor] = distance predecessors[neighbor] = u return distances, predecessors

**注释**

* `graph`是图的邻接表，表示每个顶点的相邻节点和权值。
* `start`是起始顶点。
* `distances`是距离表，记录从起始顶点到其他顶点的最短距离。
* `predecessors`是前驱节点表，记录从起始顶点到其他顶点的前驱节点。

###3. Floyd-Warshall算法Floyd-Warshall算法是一种求图的最短路径算法，可以处理有向图或无向图，并且每个顶点都有一个权值。该算法适用于所有类型的图。

**模板代码**

def floyd_warshall(graph):
 # 初始化距离表 distances = [[float('inf')] * len(graph) for _ in range(len(graph))]

 # 初始化距离表中的自身距离为0 for i in range(len(graph)):
 distances[i][i] =0 # 构造距离表 for u, v in graph.items():
 for neighbor, weight in v.items():
 distances[u][neighbor] = weight # Relax edges for k in range(len(graph)):
 for i in range(len(graph)):
 for j in range(len(graph)):
 distance = distances[i][k] + distances[k][j]

 # 如果新距离小于已知最短距离，则更新 if distance < distances[i][j]:
 distances[i][j] = distance return distances

**注释**

* `graph`是图的邻接表，表示每个顶点的相邻节点和权值。
* `distances`是距离表，记录从一个顶点到另一个顶点的最短距离。

###4. A*算法A*算法是一种求图的最短路径算法，可以处理有向图或无向图，并且每个顶点都有一个权值。该算法适用于所有类型的图。

**模板代码**

import heapqdef a_star(graph, start, goal):
 # 初始化距离和前驱节点表 distances = {node: float('inf') for node in graph}
 distances[start] =0 predecessors = {start: None}

 # 构造优先队列 queue = [(0, start)]

 while queue:
 current_distance, current_node = heapq.heappop(queue)

 # 如果当前距离大于已知最短距离，则跳过 if current_distance > distances[current_node]:
 continue for neighbor, weight in graph[current_node].items():
 distance = current_distance + weight # 如果新距离小于已知最短距离，则更新 if distance < distances[neighbor]:
 distances[neighbor] = distance predecessors[neighbor] = current_node heapq.heappush(queue, (distance, neighbor))

 return distances, predecessors

**注释**

* `graph`是图的邻接表，表示每个顶点的相邻节点和权值。
* `start`是起始顶点。
* `goal`是目标顶点。
* `distances`是距离表，记录从起始顶点到其他顶点的最短距离。
* `predecessors`是前驱节点表，记录从起始顶点到其他顶点的前驱节点。

以上四种求图的最短路径模板都可以用于不同的场景中。Dijkstra算法和A*算法适用于有向图或无向图，并且每个顶点都有一个权值。Bellman-Ford算法适用于有向图或无向图，并且每个顶点都有一个权值，能够处理负权值和循环图。Floyd-Warshall算法适用于所有类型的图，可以求出从一个顶点到另一个顶点的最短距离。