| 无向赋权图最短通路的矩阵算法 |
| |
| 引用本文： | 朱志雄,杨树清. 无向赋权图最短通路的矩阵算法[J]. 湖北工业大学学报, 2012, 0(5): 106-108,112 |
| |
| 作者姓名： | 朱志雄 杨树清 |
| |
| 作者单位： | [1]武汉市广播电视大学,湖北武汉430205 [2]武汉软件工程职业学院,湖北武汉430205 |
| |
| 摘 要： | Dijkstra算法是求赋权图最短通路中最著名的算法.但其数学的表达式却非常复杂,而且只求出起点到各点的最短通路的权.通过对赋权图进行矩阵定义以及定义相应的矩阵运算法则,就可以求出任意两点间的最短通路的权.这一算法为求赋权图的最短通路及权的编程提供了算法模型.
|
| 关 键 词： | 最短通路 赋权图矩阵 矩阵运算 |
A New Matrix Algorithm For The Shortest Path Problem |
| |
| ZHU Zhi-xiong,YANG Shu-Qing. A New Matrix Algorithm For The Shortest Path Problem[J]. Journal of Hubei University of Technology, 2012, 0(5): 106-108,112 |
| |
| Authors: | ZHU Zhi-xiong YANG Shu-Qing |
| |
| Affiliation: | 1 Engineering Wuhan Television and Radio Univ.,Wuhan 430205,China; 2 Wuhan Vocational College of Software,Wuhan 430205,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | shortest path problem a new matrix of a graph a new matrix multiplication |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
