本站原创摘 要： 最短路径问题是图论研究中的一个经典算法问题,Dijkstra算法和Floyd算法是解决任意两点间最短路径的常用办法.从局部最优到整体最优的思想出发,得出求解最短路径的一个新方法,即两点间的最短路径是途经当前最短路径集的复合路径和直达路径的最短者,然后以此方法给出求解任意两点间最短路径的一个新算法,最后简述新算法在针对特定问题时相对于经典算法的优势.
关 键 词 ： 最短路径；Dijkstra算法；Floyd算法
0 引言
最短路径问题是图论研究中的一个经典算法问题,旨在寻找图中两结点之间的最短路径.在实际应用中有着重要意义,特别是针对优选问题诸如最小成本计算、位址选择模型、节点连通性等都和图论中的最短路径问题等价,在方法论上它们有着很大程度的相似性与一致性.在求解网络图上节点间最短路径的方法中,目前国内外一致公认的较好算法有迪杰斯特拉（Dijkstra）及弗罗伊德（Floyd）算法.这两种算法中,网络被抽象为一个图论中定义的有向或无向图,并利用图的节点邻接矩阵记录点间的关联信息.在通过图的遍历搜索最短路径时,以该矩阵为基础不断进行目标值的最小性判别,直到获得最后的优化路径.虽然这两种算法总的执行时间均为O（n3）,但是Floyd算法形式上更简单些.