CAJ | 학술논문

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