图的最短路径矩阵算法

最短路径有很多算法。

今天和同学讨论概率转移矩阵时如何选择N步最大概率路径问题想到了以下内容。

问题：一个有权图(有无向都可以)对应于一个矩阵。其中矩阵元素i，j对应图中点i到点j的权。
如何找到点i切好n步到点j的所有路径中权值和最大的，最小的以及权值积最大的，最小的等等特许要求的路径的对应值呢(不求路径，只需要最后的结果)。

可以通过修改我们熟悉的矩阵乘法运算来方便实现这些要求。

矩阵乘法，积的i，j对应第一个矩阵的第i行和第二个矩阵的第j列矢量相乘结果。

现在根据题目要求相应修改这一步运算即可。

如求权值和(积)最大(小)值，那就把第一个矩阵的第i行和第二个矩阵的第j列对应相加(乘)，选最大(小)值作为结果的i，j值。

n步的话就做n次运算即可。还可以类似求x^n算法那样，运算log n次乘法。

设有m个点，则复杂度为O(m^3 log n)，而一般搜索算法的话O(k^n)k为边总数。

复杂度没有很详细的研究。

数学归纳法证明：

首先1阶出示矩阵没什么说的

然后算2阶的时候，i，j元素都是用1阶的第i行，第j列数两两相加(乘)取最大(小)值意思就是i到j两步和(积)的最大(小)值，就是i到别的一个点k，然后k再到j他们的概率相加(乘)取最大(小)值，2阶是成立的。
假设n阶成立的那么n+1阶的i，j就用n阶的第i行所有元素与1阶的第j列相加(乘)取最大(小)值
因为n阶是对的i到j的n+1步最大和(积)可以是i到其他人一点k的n步最大和(积)再加(乘)上k到j的权重，这个值肯定是i走n-1步到k再到j这条路上的最大(小)值

那么所有的k再选一个最大(小)的就是i到j所有n+1步中最大(小)的

盼望大家给出建议。

评论

2 楼 andyjojo 2009-01-15  

哈哈，这个实现应该很简单的吧

1 楼 kjj 2009-01-14  

我还以为有算法呢，原来什么都没有