论文部分内容阅读
设Ｇ＝（Ｖ，Ｅ）是一个边皆有非负权的连通无向图，设Ｚ是Ｇ的结点集Ｖ的子集。一个最小Ｓｔｅｉｎｅｒ树是Ｇ的连通子图，它含有Ｚ的全部结点，且是有最小边权和的树，一个启发式算法上ＥＩ－Ａｒｂｉ，ｐｌｅｓｎｉｋ和ｋｏｕ等人给出，按该算法得到的Ｓｔｅｉｎｅｒ树与最小Ｓｔｅｉｎｅｒ树最多只差一常数因子２（１－１／ｚ）这里ｚ＝（Ｚ）。该算法要计算出Ｚ个单源最短路径且算法的时间复杂度的Ｏ（ｚ（ｎｌｏｇｎ＋ｍ）这里