1、南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院1234南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院1.引 言南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院图图1(a)给定一个无向图给定一个无向图 (b)根为根为v6时的最小生成树时的最小生成树南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院例如，例如，addCost(v3)=2+(1+2)+(1+2)+(1+1+2)+(1+1+2)+(2+1+2)=21图图1(b)根为根为v6时的最小生成树时的最小生成树 图图2 换路后得到的图换路后得到的图
2、ijVvijijvvCostvaddCost,)(南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院v0v1v2v3v4v5v6v7v8v0025157448v12063129105v2560257645v31320610783v4515604362v57271040258v6496732047v74104865409v8855328790表表1 网络的开销矩阵网络的开销矩阵南京理工大学计算机科学与技术学院图图3 三种方法求最佳生成树三种方法求最佳生成树(a)修改过的修改过的prim算法算法(b)最佳根节点为最佳根节点为v0(c)换路后的生成树换路后的生成树南京理工大学计算机科学与技术学院图图4 用两种参数优化生成树用两种参数优化生成树(a)根据根据“最小开销值最小开销值”选择备份链路选择备份链路(b)根据根据“节点节点vi的开销和的开销和”选择备份链路选择备份链路南京理工大学计算机科学与技术学院
