一种新的最短路径算法

摘要：

定义了有向图的代价邻接矩阵和最短路径矩阵,给出了称为"乘位加比小"的一种代价邻接矩阵间的新运算.基于该矩阵运算,证明了一种称为"代价邻接矩阵乘位加比小算法"新的最短路径算法.其结果可实现有向图全局最短寻径,并且对于任意类型的有向图,总是可准确求得其最短路径.E.W.Dijkstra提出的标号法是一种公认的求最短路径的较好算法,但在某些情况下寻径结果并非最优,文中提出的新算法克服了其缺点.

关键词：Dijkstra算法、乘位加比小运算、最短路径算法、矩阵运算、路由算法

所属期刊栏目：34

分类号：TP393.03(计算技术、计算机技术)

在线出版日期：2006-01-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：778-781