Python中如何将Dijkstra输出的一维数组新增行存入n×n矩阵

问题根因 #

你定义的dijkstra方法没有设置显式返回值，Python中所有未显式写return语句的函数/方法，执行完成后默认返回None，这就是你D_path变量是NoneType的原因。

修改方案 #

1. 给dijkstra方法添加返回值：在方法末尾调用完self.printSolution(dist)之后，新增一行return dist，把计算得到的最短距离数组返回。
2. 优化矩阵赋值逻辑：不需要额外定义row变量嵌套包裹D_path，直接把返回的dist数组追加到matrix中即可，避免结果多一层嵌套。

修正后完整代码 #

import sys
import numpy as np

 
class Graph():
 
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]
 
    def printSolution(self, dist):
        print("Vertex tDistance from Source")
        for node in range(self.V):
            print(node, "t", dist[node])
 
    # 查找未加入最短路径树的节点中距离最小的节点
    def minDistance(self, dist, sptSet):
        min = sys.maxsize
        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v
        return min_index
 
    # Dijkstra单源最短路径实现
    def dijkstra(self, src):
        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V
 
        for cout in range(self.V):
            u = self.minDistance(dist, sptSet)
            sptSet[u] = True
            # 更新邻接节点距离
            for v in range(self.V):
                if self.graph[u][v] > 0 and sptSet[v] == False and dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]
 
        self.printSolution(dist)
        return dist # 新增返回距离数组
 
 
# 测试代码
g = Graph(9)
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
           [4, 0, 8, 0, 0, 0, 0, 11, 0],
           [0, 8, 0, 7, 0, 4, 0, 0, 2],
           [0, 0, 7, 0, 9, 14, 0, 0, 0],
           [0, 0, 0, 9, 0, 10, 0, 0, 0],
           [0, 0, 4, 14, 10, 0, 2, 0, 0],
           [0, 0, 0, 0, 0, 2, 0, 1, 6],
           [8, 11, 0, 0, 0, 0, 1, 0, 7],
           [0, 0, 2, 0, 0, 0, 6, 7, 0]
           ]

matrix=[] 
for i in range(9):
    D_path = g.dijkstra(i)
    matrix.append(D_path) # 直接将距离数组作为行加入矩阵
print(matrix)

修改后matrix就是9×9的最短距离矩阵，每行对应以对应索引节点为源点的最短距离结果。

内容的提问来源于stack exchange，提问作者znz