|
|||||
|
|
| 用宽度优先搜索求网络图的最短路径 | |
| 引用本文： | 杭省策,张选平.用宽度优先搜索求网络图的最短路径[J].西安工程科技学院学报,1996(3). |
| 作者姓名： | 杭省策 张选平 |
| 作者单位： | 交通大学管理学院(杭省策)，西安交通大学计算系(张选平) |
| 摘 要： | 在对网络图变换的基础上引入了简单连通图的准生成根树的概念，并由此给出了求网络图最短路径的一种新算法．该算法与以往算法的区别在于它改变了网络图的拓扑结构，从而使搜索能够在结构非常简单的树状图上进行．该算法用最多不超过｜Ｖ｜－１层的扩展，即可找出图中从源点出发到其余顶点或任意两点间的最短路径． |
| 关 键 词： | 最短路径 准生成根树 宽度优先搜索 |
| 本文献已被 CNKI 等数据库收录！ | |