论文部分内容阅读
给定一个无向图G=（V, E;w;s，t），其中s，t是两个固定顶点，w(:)E→R+是边的长度函数。最短路是指所有路中长度最小者。次短路是指长度比最短路严格大的所有路中的最小者。严格第三短路是指长度比次短路严格大的所有路中的最小者。最短路问题是图论的核心问题之一，最短路算法是许多更深层算法的基础。次短路问题就是在最短路网络上解决的，而严格第三短路问题目前还没有相关的算法。本文提出一个O(n4)多项式时间算法解决正权重无向图中的严格第三短路问题。 本文由以下五章构成。 第一章，回顾问题的由来，给出到目前为止的一些研究成果; 第二章，给出本文所涉及的定义，概念和符号; 第三章，给出最短路问题、最小费用流问题相关的算法和定理; 第四章，讨论次短路问题，给出相应的算法; 第五章，讨论严格第三短路问题，给出相应的算法; 最后，给出相关结论以及未来的研究方向。