CAJ | 학술논문

对于求解小规模无回路网络的最短路径这一问题,目前大多数算法都是基于Dijkstra算法或者穷举法的思想,不仅计算量大而且操作复杂.文中在深入分析已有算法的基础上,给出了一种新的简单易行的方法.该算法通过不断消去中间节点和弧以简化图的结构,既能快速地计算出源点到目的节点的最短路径,又能直观地找出最短路.最后算法通过具体实例分析表明,该算法不仅思想简便、易于操作,同时有效地降低了算法复杂度,是计算小规模无回路网络的一种行之有效的算法.
대우구해소규모무회로망락적최단로경저일문제,목전대다수산법도시기우Dijkstra산법혹자궁거법적사상,불부계산량대이차조작복잡.문중재심입분석이유산법적기출상,급출료일충신적간단역행적방법.해산법통과불단소거중간절점화호이간화도적결구,기능쾌속지계산출원점도목적절점적최단로경,우능직관지조출최단로.최후산법통과구체실례분석표명,해산법불부사상간편、역우조작,동시유효지강저료산법복잡도,시계산소규모무회로망락적일충행지유효적산법.
For solving the shortest path on DAG,most of algorithms are based on Dijkstra algorithm or brute-force method,it's not only computationally expensive and complicated to operate. Based on the existing shortest path algorithm,propose a new simple method. The algorithm continuously deletes intermediate nodes and arcs to simplify the structure,not only can quickly calculate the shortest path from the source node to the destination node,but also find shortest paths easily. Finally algorithm through the concrete example analysis shows that,this algorithm is easy to operate,and at the same time,effective to reduce the algorithm complexity. It is a feasible algorithm of cal-culating loop-free network.