0

我是 Python 的初学者，遇到这个问题已经有一段时间了。任何纠正问题的建议都是有价值的。下面是用于查找最短路径的代码，使用 Dijkstra 算法。我有成本矩阵和源作为输入。

def dijkstra(cost_matrix,source):
    n = 20
    dist = [0 for row in range(20)]
    visited = [0 for row in range(20)]
    for j in range(20):
        visited[j] = "False"
    visited[source] = "True"
    for i in range(20):
        dist[i] = cost_matrix[source][i]
    prev_min = source
    for k in range(20):
        minimum = min(dist)
        minimum2 = min(minimum,n)
        for i in range(20):
            if dist[i] > (cost_matrix[prev_min][minimum2] + cost_matrix[minimum2][i]):
                dist[i] = cost_matrix[prev_min][minimum2] + cost_matrix[minimum2][i]
        visited[minimum2] = "True"
        prev_min = minimum2
    return dist

计算 cost_matrix 的代码

def matrix():
    k = 30
    b_ij = [[0 for row in range(20)] for col in range(20)]
    a_ij = [[0 for row in range(20)] for col in range(20)]
    cost_matrix = [[0 for row in range(20)] for col in range(20)]
    for i in range(20):
        for j in range(20):
            rand = random.randint(0,8)
            b_ij[i][j] = rand
            b_ij[j][i] = rand
    while(k > 0):
        rand1 = random.randint(0,19)
        rand2 = random.randint(0,19)
        a_ij[rand1][rand2] = 200
        a_ij[rand2][rand1] = 200
        k = k - 1
    for i in range(20):
        for j in range(20):
            if a_ij[i][j] != 200:
                rand = random.randint(0,8)
                a_ij[i][j] = rand
                a_ij[j][i] = rand
    for i in range(len(a_ij)):
        for j in range(len(b_ij[0])):
            for k in range(len(b_ij)):
                cost_matrix[i][j] += a_ij[i][k] * b_ij [k][j]

错误信息：

Traceback (most recent call last):
  File "ass1.py", line 60, in <module>
    print(dijkstra(cost_matrix, 1))
  File "ass1.py", line 45, in dijkstra
    dist[i] = cost_matrix[source][i]
TypeError: 'NoneType' object is not subscriptable
4

2 回答 2

2

您还没有在创建cost_matrix. 您发布了矩阵函数的代码，但没有发布使用矩阵函数的代码。

但是，看起来问题在于您的matrix函数没有返回任何内容。它只是创建一个矩阵并将其丢弃。您需要return cost_matrix在该函数的末尾添加。

于 2012-10-13T05:31:04.813 回答
0

cost_matrix 或 cost_matrix[source] 的值为 None，但它应该是一个列表。

在该行之前打印它们：

dist[i] = cost_matrix[source][i]

找出问题所在。

顺便说一句，你可能应该使用 numpy 来处理这类事情。

于 2012-10-13T06:30:40.957 回答