拆边法求最短路径

对于给定赋权的一个无向图，给出子图、无效路径以及可去边的定义，并在推导出有关定理的基础上，举例说明用拆边法求最短路径的方法：先利用局部比较法在图中拆去可去边，再利用最短路径相同的等价性对图化简，从而求出最短路径。