一种图的st编号路径长度算法
【出 处】:
图论
平面图
st-编号
最短路径
最长路径
【作 者】:
刘阳
;
晏立
【摘 要】通过对无向图的顶点标注st-编号,可以使它转换为一个有向图,根据有向图的方向可计算出从源点到汇点的路径长度。用DFS算法可计算出st-编号,但一个图有多种不同的st-编号方法,不能确定图的最长路径或者最短路径。使用移除法,连续移除根据时间戳选择出来的顶点,计算出图的st-编号,能够确定图的最长路径或者最短路径。st-编号路径长度在计算网络动态路由、计算最少着色数、减少框图高度等问题上有广泛的应用。
相关热词搜索:
上一篇:上海市微型电脑应用学会召开七届三次常务理事会扩大会议暨中国科协第五届科协会员日活动
下一篇:基于块信息的异模图像配准算法