矩阵求解无向图经过n条边最短路问题
  • 板块学术版
  • 楼主akahoshi
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/5/11 13:24
  • 上次更新2024/5/11 17:56:43
查看原帖
矩阵求解无向图经过n条边最短路问题
1295409
akahoshi楼主2024/5/11 13:24

例题

已经学完了路径数量的解法 在学求解无向图经过n条边最短路问题的时候

书上的解法是定义矩阵的广义乘法

M×M=∑a=1Nmin⁡(M(i,a)+M(a,j))M \times M = \sum_{a=1}^{N} \min({M(i, a)+M(a, j)})

则邻接矩阵M的广义幂G=MnG=M^n为无向图经过n条边最短路路径长

个人不太理解的是为何在重新定义了广义乘法之后仍然能用乘法的运算律化成幂的形式而使用快速幂求解，如何证明其成立

2024/5/11 13:24