独立多约束最短路径选择

摘要

The shortest path problem is one of the most important issues in communication and transportation as well as an NP-complete problem. How to select an appropriate cost function is essential to solve this problem,.This paper focuses on the independent multiple constraints path finding and provides a theoretical framework on selecting the cost function for the independent multiple constraints path finding. Finally the framework is applied to shortest path selecting, and the result shows that the instantiation cost function can successfully help find a feasible path.%多约束最短路径问题一直以来都是通信、交通等领域最主要的问题之一,该问题是一个NP问题.在解决多约束最短路径选择中,代价函数的选择至关重要.针对相互独立的乘性多约束条件,提出一种代价函数的选取框架,并将此框架应用于两约束的最短路径选择中,实验结果表明,能够很好的发现最短路径.