论文部分内容阅读
最短路问题是一个经典的最优化问题.最短路问题在现实生活中有着广泛的应用，比如交通运输、网络设计等领域.该问题已被很好地解决。到目前为止，对该问题的研究已取得了一些理论研究成果，为实际应用奠定了基础.
但是，随着社会的发展，出现了许多限制性的最短路问题。本文主要研究了两类限制性的最短路问题：(1)有特殊顶点限制的最短路问题；(2)有特殊边限制的最短路问题.分别给出了解决这两类问题的多项式时间算法，并且分析了算法的时间复杂性.
本文包括以下四章；
第一章：回顾了问题的由来，介绍了理论的形成和最近的一些研究成果.
第二章：给出了文中用到的有关图论、组合最优化和NP-完备性理论方面的基本概念、符号和术语.
第三章：分别讨论了有特殊顶点限制的最短路问题和有特殊边限制的最短路问题，给出了多项式算法和复杂性分析.
第四章：总结全文，并给出未来的研究方向.