10.3969/j.issn.1000-3428.2009.14.029
无回路网络中最短路问题的高效算法
无回路网络是一类重要的网络,给出在无回路网络中求解最短路树形图和任意顶点对间最短路的高效算法.该算法将顶点进行重新编号,结合广度优先探索法,从源顶点出发依次搜索每个顶点的所有出弧,并在弧的头部进行权值变换操作,可以得到最短路树形图和任意顶点对间最短路,算法复杂度分别为O(m)和O(m(n-m1/2)).该算法思想简便、复杂度低、易于操作.
根、无回路网络、最短路树形图
35
TP311(计算技术、计算机技术)
国家"973"计划基金资助项目613610202
2009-08-19(万方平台首次上网日期,不代表论文的发表时间)
共4页
84-86,103