摘要： 无回路网络是一类重要的网络，给出在无回路网络中求解最短路树形图和任意顶点对间最短路的高效算法。该算法将顶点进行重新编号，结合广度优先探索法，从源顶点出发依次搜索每个顶点的所有出弧，并在弧的头部进行权值变换操作，可以得到最短路树形图和任意顶点对间最短路，算法复杂度分别为O(m)和O(m(n-m1/2))。该算法思想简便、复杂度低、易于操作。
关键词：

关键词: 根, 无回路网络, 最短路树形图

Abstract: Directed Acyclic Graph(DAG) is a kind of important network. A high-efficient algorithm to seek the shortest path arborescence and all shortest paths between any two vertices in DAG is presented. Arranging the vertices over again and using breadth first search for reference, this algorithm checks all out-arcs of each vertex starting with the source, and transforms the length values of the shortest paths at the head of each arc,and then it can get the shortest path arborescence and all shortest paths between any two vertices respectively in time O(m)and O(m(n-m1/2)). Correlative analysis and instances indicate that this algorithm is superior to other current algorithms in respect of computing complexity and operation.

Key words: root, Directed Acyclic Graph(DAG), shortest path arborescence

中图分类号: 

• TP311