论文部分内容阅读
寻找同时满足多个独立的QoS约束的路径是一个NP完全问题。提出一种解决多约束路径问题的有效算法———多约束最小跳路径算法(MHMCA),该算法首先利用Bellman Ford最短路径算法进行标记,并删除图中的无用链路,在简化后的图中使用基于堆栈的深度优先搜索算法寻找所有满足约束的最小跳可行路径。最坏情况下,算法的时间复杂度为O(n3)。仿真结果表明,该算法寻找具有最小跳可行路径的成功率高,接近于最优算法。