【出 处】： 图论 平面图 st-编号 最短路径 最长路径

【作 者】： 刘阳 ; 晏立

【摘 要】通过对无向图的顶点标注st-编号,可以使它转换为一个有向图,根据有向图的方向可计算出从源点到汇点的路径长度。用DFS算法可计算出st-编号,但一个图有多种不同的st-编号方法,不能确定图的最长路径或者最短路径。使用移除法,连续移除根据时间戳选择出来的顶点,计算出图的st-编号,能够确定图的最长路径或者最短路径。st-编号路径长度在计算网络动态路由、计算最少着色数、减少框图高度等问题上有广泛的应用。