dijkstra 算法求最短路径（Python）

Question

从键盘上输入一个图的基本信息（图用邻矩阵表示）
1）首先输入图的结点数﹣> num
2）依次输入图的各条边

Answer 1

• 这个问题的回答你可以参考下: 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基于相关博客总结生成:

  我可以解决该问题。

  解决方案如下：

  1. 首先，需要导入 heapq 库，它是Python内置的二叉堆实现，可用于实现Dijkstra算法中的优先队列，代码如下：

  import heapq
  

  1. 接着，需要从键盘读取用户输入的邻接矩阵，代码如下：

  n = int(input("请输入图的节点数量："))
  matrix = []
  for i in range(n):
      row = list(map(int, input(f"请输入第{i+1}行邻接矩阵元素，用空格隔开：").split()))
      matrix.append(row)
  

  在上述代码中，首先读取节点数量，然后通过循环逐行读取邻接矩阵元素，转换为整数列表，并添加到 matrix 列表中。

  1. 接下来，需要读取用户输入的起点编号，并将其转换为可用于列表索引的形式，再作为 Dijstra 算法的参数进行计算，代码如下：

  start = input("请输入起点编号：")
  start_index = ord(start) - 97  # 将字母转换为对应的列表索引
  

  在上述代码中，首先读取起点编号，然后将其转换为小写字母，再将其转换为对应的列表索引，这里假定起点编号是小写字母。

  1. 最后，进行 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}")