论文部分内容阅读
最短路问题作为图论和复杂网络中经典问题,现在在日常生活中,也出现在许许多多方面,比如通信网络,交通网络,旅行商问题中。然而用来求解最短路径的问题的解法也是数见不鲜,其中最典型的要数Dijkstra算法、Ford算法和Floyd算法。然而Dijkstra算法只可求出2个指定节点间的最短距离,Ford算法就只可以求出指定始发点的最短路径,而Floyd算法计算过程相当繁琐。最重要的是,这些算法都是仅仅能解决两节点间的1条最短路。而在实际生活中,我们有时还会因为一些给定的前提条件需要求出两点间次短、渐次短路径。根据以上的不足,本文提出了基于矩阵运算的最短路径优化算法,主要内容如下:1.针对Ford算法进行改进,提出了一种固定始发点的矩阵消去算法,通过寻找从一个固定始发点到其他顶点的路径,其中包括不经过别的顶点,经过一个顶点、经过两个顶点等等逐步迭代,找出从固有始发点到其它的顶点间的最短路。2.给出基于矩阵自定义运算的改良算法。本算法是凭借一种自定义的矩阵运算来求出一个代表每2个节点间距离的路权修正矩阵,然后用路权修正矩阵和原本的距离矩阵来比较,选择2个矩阵中相应较小的元素,组成当前的最短路权矩阵,接着,通过有限次迭代,从而获得各个顶点间的最短路径。并用MATLAB实现,将这种算法运用到随机的大规模复杂网络中去,从运行时间折线图上看出这种算法在节点数到达较大的数量后,算法速度显著提高,在稀疏网络中,该算法的效率特别高,这表明该算法的有效性。最终,经过真实的应用场景表明了这种算法的实用性。3.通过对距离矩阵和路径矩阵的迭代、替换操作,不断从一个节点出发寻找其后继节点,同时通过比较路径长短得到两点间最短路径、次短路径、渐次短路径,并用一个实际例子对该算法的实用价值加以说明。最后,在一个大型网络的实际例子中,通过MATLAB对该算法进行仿真,求得指定顶点间最短、次短、渐次短路径说明该算法能够在复杂大规模随机网络中得到应用。