dijkstra 算法求最短路径（Python）
从键盘上输入一个图的基本信息（图用邻矩阵表示）
1）首先输入图的结点数﹣> num
2）依次输入图的各条边
- 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7418583
- 这篇博客你也可以参考下：用类似Dijkstra算法的思想求解数独（Python）
- 除此之外, 这篇博客: 基于Dijkstra算法的带权有向图最短路径问题求解Python实现中的 另一个例子用Python实现 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
用Python和Numpy实现寻找任意两点之间最小路径的算法，并用下图进行测试, 得到节点s和t之间的最短路径。
对于上面这个图，Dijkstra算法的步骤如下：
1.先找到距离s点最近的点，即w
2.然后看与w相连接的点通过w再到那个点的距离近还是直接从s到这个点的距离近，由上图我们可以知道，与w相连的点是t和z，而t和z并不与s直接相连，因此更新最短距离数组和前驱数组
3.接着对距离s点第二近的点“X”重复第二个步骤，直到都执行完毕。（目的是看与“X”相连的点能否借助“X”获得更近的路径，即经过“X”，这就是上面的“借东风”）
下面的代码中，点s,v,u,w,z,t分别表示为点1,2,3,4,5,6
import numpy as np import copy def main(): #无穷大 infinity = float('inf') a = infinity #构建邻接矩阵 adjacency_matrix = np.array([[a,6,5,3,a,a], [a,a,a,1,a,3], [a,a,a,1,2,a], [a,a,a,a,9,7], [a,a,a,a,a,5], [a,a,a,a,a,a]]) #构建距离数组 dist = np.array([0,6,5,3,a,a]) #构建前驱数组 precursor = np.array([-1,1,1,1,-1,-1]) #初始集合 S = {1} V = {1,2,3,4,5,6} V_subtract_S = V - S for i in range(len(V_subtract_S)-1): dist_copy = [] V_subtract_S_list = list(V_subtract_S) for j in V_subtract_S: dist_copy.append(dist[j - 1]) min_index = dist_copy.index(min(dist_copy)) # 查找dist_copy中最小的元素的位置 S.add(V_subtract_S_list[min_index]) current_node = V_subtract_S_list[min_index] V_subtract_S = V - S for j in V_subtract_S: dist_copy.append(dist[j - 1]) for j in range(adjacency_matrix.shape[1]): if adjacency_matrix[current_node-1][j] < a: if dist[current_node-1] + adjacency_matrix[current_node-1][j] < dist[j]: dist[j] = dist[current_node-1] + adjacency_matrix[current_node-1][j] precursor[j] = current_node #打印最佳路径 temp = 1 path = [] path.insert(0, 6) precursor = list(precursor) front_code = precursor[5] while temp: path.insert(0,front_code) #front_code的数字对应的另一个节点 front_code_index = path[0] - 1 front_code = precursor[front_code_index] if front_code == 1: temp = 0 path.insert(0,1) for i in path: if i == 1: path[path.index(i)] = 's' if i == 2: path[path.index(i)] = 'v' if i == 3: path[path.index(i)] = 'u' if i == 4: path[path.index(i)] = 'w' if i == 5: path[path.index(i)] = 'z' if i == 6: path[path.index(i)] = 't' print(path)运行结果：
- 以下回答由chatgpt基于相关博客总结生成:
我可以解决该问题。
解决方案如下：
- 首先，需要导入 heapq 库，它是Python内置的二叉堆实现，可用于实现Dijkstra算法中的优先队列，代码如下：
import heapq- 接着，需要从键盘读取用户输入的邻接矩阵，代码如下：
n = int(input("请输入图的节点数量：")) matrix = [] for i in range(n): row = list(map(int, input(f"请输入第{i+1}行邻接矩阵元素，用空格隔开：").split())) matrix.append(row)在上述代码中，首先读取节点数量，然后通过循环逐行读取邻接矩阵元素，转换为整数列表，并添加到 matrix 列表中。
- 接下来，需要读取用户输入的起点编号，并将其转换为可用于列表索引的形式，再作为 Dijstra 算法的参数进行计算，代码如下：
start = input("请输入起点编号：") start_index = ord(start) - 97 # 将字母转换为对应的列表索引在上述代码中，首先读取起点编号，然后将其转换为小写字母，再将其转换为对应的列表索引，这里假定起点编号是小写字母。
- 最后，进行 Dijkstra 算法的实现，代码如下：
dist = [float('inf')] * n dist[start_index] = 0 heap = [(0, start_index)] while heap: (d, node) = heapq.heappop(heap) if d > dist[node]: continue for nei, weight in enumerate(matrix[node]): if weight > 0: new_dist = dist[node] + weight if new_dist < dist[nei]: dist[nei] = new_dist heapq.heappush(heap, (new_dist, nei)) for i, d in enumerate(dist): print(f"起点 {chr(start_index+97)} 到节点 {chr(i+97)} 的最短距离为：{d}")在上述代码中，首先初始化距离列表 dist，将起点到起点的距离设置为 0，其他节点的距离设置为无穷大。
然后使用优先队列 heap 存储节点和距离，起始状态为 (0, start_index)，即起点到自己的距离为 0。
在 while 循环中，每次从 heap 中弹出距离最小的节点，并更新其邻居节点的距离。
最后，循环遍历所有节点，输出起点到各个节点的最短距离。
完整代码如下：
import heapq n = int(input("请输入图的节点数量：")) matrix = [] for i in range(n): row = list(map(int, input(f"请输入第{i+1}行邻接矩阵元素，用空格隔开：").split())) matrix.append(row) start = input("请输入起点编号：") start_index = ord(start) - 97 dist = [float('inf')] * n dist[start_index] = 0 heap = [(0, start_index)] while heap: (d, node) = heapq.heappop(heap) if d > dist[node]: continue for nei, weight in enumerate(matrix[node]): if weight > 0: new_dist = dist[node] + weight if new_dist < dist[nei]: dist[nei] = new_dist heapq.heappush(heap, (new_dist, nei)) for i, d in enumerate(dist): print(f"起点 {chr(start_index+97)} 到节点 {chr(i+97)} 的最短距离为：{d}")