最短路算法(dijstra算法)的研究

A New Integrated Heuristic Algorithm for Multicast

Dijstra标号算法是求从一点到网络其它各点之间最短路的重要算法,而最小生成树是求网络各点之间相互连接的整体代价最小的算法,两者之间算法过程以及思路都不同。然而,本文对这两个算法进行研究,发现这两种算法的本质是一致的。接着对算法进行推广,一种综合算法,并应用到组播路径构造上,经对许多事例分析,发现该算法不仅很好地解决了无约束组播和有时延约束组播的近似最优解的问题,同时对部分有时延和时延抖动组合约束问题也能进行快速求解,且复杂度不超过O(kmn2)。

In this paper,by investigation of the shortest pathway and the minimum span tree’s algorithm,we find that the two algorithms are the same in essence. So we present a new algorithm that is a induces of them,named ICOA(Integrated Optimization Cost Algorithm ). In allusion to multicast,we ulterior present an algorithm (M-ICOA). M-ICOA is a good algorithm to solve the non-constrained or delay-constrained Steiner Tree problem. And it can solve some delay and delay variation constrained Steiner Tree problem too.