### 关于路径图的 Python 代码实现 #### Dijkstra 算法实现单源最短路径计算 对于给定的一个加权有向图 G=(V,E)，其中 V 是顶点集合，E 是边集。每条边都有一个非负权重 w(u,v) 表示从 u 到 v 的距离。Dijkstra 算法可以用来找到从起始节点到所有其他节点的最短路径。 ```python import heapq def dijkstra(graph, start): n = len(graph) dist = [float('inf')] * n prev = [-1] * n visited = [False] * n pq = [(0, start)] while pq: d, node = heapq.heappop(pq) if not visited[node]: visited[node] = True for neighbor, weight in graph[node].items(): new_dist = d + weight if new_dist < dist[neighbor]: dist[neighbor] = new_dist prev[neighbor] = node heapq.heappush(pq, (new_dist, neighbor)) return {'distances': dist, 'prev_nodes': prev} ``` 此函数接收邻接表形式表示的 `graph` 和起点索引作为输入参数，并返回两个列表：一个是各结点间的最小花费；另一个用于重建实际路线[^3]。 为了打印具体的路径，可以根据前驱数组构建路径： ```python def reconstruct_path(prev, target): path = [] at = target while at != -1: path.append(at) at = prev[at] path.reverse() return path ``` 调用上述方法并传入目标位置即可获取完整的行走轨迹[^1]。 #### Floyd-Warshall 多源最短路径算法 当涉及到任意两点间的所有可能连接时，则需采用更通用的方式——Floyd-Warshall 算法来解决问题。它能够处理带负数权重的情况（只要不存在负环），并且适用于稠密图结构。 ```python def floyd_warshall(dist): """The function computes shortest paths between pairs of vertices.""" num_vertices = len(dist) # Initialize predecessor matrix to store the next vertex on the best known route from i to j. pred = [[None]*num_vertices for _ in range(num_vertices)] for k in range(num_vertices): for i in range(num_vertices): for j in range(num_vertices): # If there's a shorter way through intermediate point k update distance and set up predecessors accordingly. if dist[i][k]+dist[k][j]<dist[i][j]: dist[i][j]=dist[i][k]+dist[k][j] pred[i][j]=pred[k][j] or k return {"distance": dist,"predecessor": pred } ``` 这段程序会更新全局的距离矩阵以及记录中间节点的信息以便后续查询具体路径[^2]。