摘要
对于给定赋权的一个无向图,给出子图、无效路径以及可去边的定义,并在推导出有关定理的基础上,举例说明用拆边法求最短路径的方法:先利用局部比较法在图中拆去可去边,再利用最短路径相同的等价性对图化简,从而求出最短路径。
In this paper, we compare the partial side of a son graph in a mother graph and remove the re-movable sides. Then the shortest path of a graph is easily got when the graph gets more and more simple but the shortest paths of the two graphs are identical.
关键词
最短路径问题
无向图
子图
可去边
拆边法
无效路径
动态规划
the problem of the shortest path
no-direction graph
son graph
removable side
the method of removing side
