一种图的st编号路径长度算法

• 作者: 刘阳 晏立
• 来源期刊: 微型电脑应用
• 学科: 工学
• 关键词: 图论 平面图 st-编号 最短路径 最长路径
• 年，卷（期）: 2013,（1）
• 所属期刊栏目: 技术交流
• 页码范围: 61-64
• 页数: 4页
• 分类号: TP311
• 字数: 4002字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	晏立	江苏大学计算机科学与通信工程学院	27	270	7.0	16.0
2	刘阳	江苏大学计算机科学与通信工程学院	12	158	4.0	12.0