一种新的最短路径算法

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

A New Matrix Operator-Based Algorithm to the Shortest Path Problem

This paper defines the adjacent cost matrix and the path matrix based on the directed weighted-graph, and defines a new operator that "summarization then minimum" replace "multiplication then summarization" between two adjacent cost matrixs, named "minimum of summarization sequence between two multiplication position elements of the two matrixs". Based on this new matrix operator, this paper proposes a new algorithm to the shortest path problem within a directed graph. This algorithm can get the global shortest path out for any types of graph. Dijkstra algorithm is a well-known good solution to the shortest path problem, but it will result out a fake path to some kinds of graph. The algorithm presented by this paper completely overcome this phenomena out of Dijikstra algorithm.