无向赋权图最短通路的矩阵算法

A New Matrix Algorithm For The Shortest Path Problem

Dijkstra算法是求赋权图最短通路中最著名的算法.但其数学的表达式却非常复杂,而且只求出起点到各点的最短通路的权.通过对赋权图进行矩阵定义以及定义相应的矩阵运算法则,就可以求出任意两点间的最短通路的权.这一算法为求赋权图的最短通路及权的编程提供了算法模型.

In graph theory,the shortest path problem is the problem of finding a path between two vertices（or nodes） in a graph such that the sum of the weights of its constituent edges is minimized.The most important algorithms for solving this problem is Dijkstra＇algorithm.In this article,we can define a new matrix of a graph which edges represent segments of road and are weighted by the time needed to travel that segment.on the basis of the matrix,we define a its new operation-addition.We can use simple mathematical formula to express Dijkstra＇algorithm.