图两顶点最短路径实现遇TypeError：前驱矩阵或路径函数问题求助

问题背景 #

我用WeightedAdjacencyMatrix类实现了带权邻接矩阵图，其中包含Floyd-Warshall算法生成最短路径权重矩阵D和前驱矩阵P，还有pair_shortest_path函数用来根据这两个矩阵获取指定源点到目标点的最短路径和权重。但运行测试代码时触发了类型错误。

测试代码 #

G = WeightedAdjacencyMatrix(4)
G.add_edge(0, 1, 2)
G.add_edge(1, 2, 3)
G.add_edge(2, 3, 1)

D, P = G.floyd_warshall()
w, path = pair_shortest_path(D, P, 0, 3)

print("Shortest path weight:", w)  # 预期输出: Shortest path weight: 6
print("Shortest path:", path)  # 预期输出: Shortest path: [0, 1, 2, 3]

错误信息 #

s = P[s][t]
TypeError: list indices must be integers or slices, not NoneType

相关代码 #

WeightedAdjacencyMatrix类 #

import math
import copy

class WeightedAdjacencyMatrix:
    """带权图的邻接矩阵实现"""

    __slots__ = ['_W']

    def __init__(self, size, edges=[], weights=[]):
        """初始化指定节点数的带权邻接矩阵图

        参数说明：
        size -- 图的节点数量
        edges -- 边的列表，每个元素是二元组表示边的两个端点，默认空列表
        weights -- 边的权重列表，长度需与edges一致，默认空列表
        """
        self._W = [[math.inf] * size for _ in range(size)]

        for i in range(size):
            self._W[i][i] = 0

        for edge, weight in zip(edges, weights):
            self.add_edge(edge[0], edge[1], weight)

    def add_edge(self, u, v, weight):
        """添加无向边u-v，指定权重

        参数说明：
        u -- 顶点ID（0-based）
        v -- 顶点ID（0-based）
        weight -- 边的权重
        """
        self._W[u][v] = weight
        self._W[v][u] = weight

    def floyd_warshall(self):
        """Floyd-Warshall算法计算所有节点对的最短路径

        返回两个矩阵：D是所有节点对的最短路径权重矩阵，P是前驱矩阵（教材中的PI矩阵）
        注意：此方法不能修改图自身的权重矩阵
        """
        n = len(self._W)

        # 深拷贝权重矩阵作为初始D矩阵
        D = copy.deepcopy(self._W)

        # 初始化前驱矩阵为None
        P = [[None]*n for _ in range(n)]

        # 计算所有节点对的最短路径
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if D[i][k] + D[k][j] < D[i][j]:
                        D[i][j] = D[i][k] + D[k][j]
                        P[i][j] = k

        return D, P

pair_shortest_path函数 #

import math

def pair_shortest_path(D, P, s, t):
    """根据Floyd-Warshall生成的D和P矩阵，获取源点s到目标点t的最短路径及权重

    参数说明：
    D - 最短路径权重矩阵
    P - 前驱矩阵
    s - 源顶点ID
    t - 目标顶点ID

    返回值：(w, path)，w是路径权重，path是顶点列表（从s到t）；若不存在路径则返回(math.inf, [])
    """
    if D[s][t] == math.inf:
        # s到t无路径
        return math.inf, []

    # 利用前驱矩阵构建路径
    path = [s]
    while s != t:
        s = P[s][t]
        path.append(s)
    # 获取路径权重
    w = D[path[0]][path[-1]]
    return w, path

问题原因分析 #

1. 前驱矩阵初始化缺失：当前代码中P矩阵初始化为全None，但对于直接相连的节点对（比如0→1），P[0][1]应该被初始化为0（即直接边的起点），而非保持None。这导致路径回溯时无法找到初始直接边的前驱节点。
2. 前驱矩阵更新逻辑错误：Floyd-Warshall核心循环中，找到更短路径i→k→j时，错误地将P[i][j]设为k，正确的做法应该是继承k→j路径的前驱节点，这样才能形成完整的路径链。
3. 路径生成逻辑错误：原函数试图正向从s跳到t，但不符合标准前驱矩阵的回溯逻辑，应该从t反向回溯到s，再反转得到正向路径。

修复方案 #

1. 修正Floyd-Warshall中的前驱矩阵初始化与更新逻辑 #

def floyd_warshall(self):
    n = len(self._W)
    D = copy.deepcopy(self._W)
    P = [[None]*n for _ in range(n)]

    # 初始化前驱矩阵：直接相连的节点i→j，前驱设为i
    for i in range(n):
        for j in range(n):
            if i != j and D[i][j] != math.inf:
                P[i][j] = i

    # 执行Floyd-Warshall核心循环
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if D[i][k] + D[k][j] < D[i][j]:
                    D[i][j] = D[i][k] + D[k][j]
                    # 更新前驱：继承k→j路径的前驱
                    P[i][j] = P[k][j]

    return D, P

2. 修正pair_shortest_path函数的路径生成逻辑 #

def pair_shortest_path(D, P, s, t):
    if D[s][t] == math.inf:
        return math.inf, []

    # 反向构建路径：从t回溯到s
    path = [t]
    current = t
    while current != s:
        prev = P[s][current]
        if prev is None:
            return math.inf, []
        path.append(prev)
        current = prev
    # 反转得到正向路径
    path.reverse()
    w = D[s][t]
    return w, path

测试验证 #

修复后运行测试代码，输出将符合预期：

Shortest path weight: 6
Shortest path: [0, 1, 2, 3]

内容的提问来源于stack exchange，提问作者РуфінЗавгородніМаркТВ13