基于极小代数赋权有向图最短路径求解算法

An Efficient Algorithm for Solving Shortest Path of Weighted Digraph Based on Min-algebra

应用极小代数给出了求解简单有向赋权图最短路径问题的代数算法.该算法基于赋权有向图的直接距离矩阵A,在极小代数意义下计算k步最短路径距离矩阵Ak和最短路径距离矩阵A+,并依此确定出赋权有向图的最短路径以及最少步数最短路径.与Dijkstra算法相比较,所提出的代数算法求解路径规划问题能够较快地得到特定的最短路径及其长度.

An efficient algorithm based on min-algebra is developed for solving the shortest path problem in a simple weighted directed graph.This algorithm calculates shortest path matrix Ak of k steps（k exponential matrix）and shortest path matrix A＋with min-algebra by the direct distance matrix A of directed graph.Accordingly,the shortest path and the shortest path of minimal steps in the directed graph can be determined.The certain shortest path and its length are obtained by the proposed algorithm faster than Dijkstra algorithm.