论文部分内容阅读
最短路问题是图论、组合数学、计算机科学、运筹学和管理科学等学科的一个经典而且基本的问题，其不仅具有丰富的研究内容，而且具有广泛的应用基础，甚至有些著名问题尚待解决。本文无法对所有的最短路问题展开研究，选择了非负权单源点最短路问题、负权单源点最短路问题两类最基本的最短路问题作为研究对象，力求在这些问题的计算方法上取得突破，同时试图解决一些不够完善的问题。
自1959年以来，Dijkstra算法一直是非负权单源点最短路问题公认的最好算法之一，也是应用最为广泛的算法之一。本文指出Dijkstra算法存在多种形式，且相互之间存在一定差异。为此，本文对各种形式的Dijkstra算法进行了总结，得到了比普遍流行的Dijkstra算法更为优秀的新形式--新Dijkstra算法，新Dijkstra算法能够节省计算量。
一般说来，Dijkstra算法仅仅能够求得从始点到任意点的一条最短路径。出于管理决策需要，需要求得从始点到任意点的所有最短路径。本文对新形式的Dijkstra算法进行了推广，得到了能够求得从始点到任意点的所有最短路径的广义Dijkstra算法。
Dijkstra算法负权化长期以来是一个广受关注的经典问题，它要求把Dijkstra算法有效地推广到负权情形。Ford、Edmonds和Karp等人先后给出了能够解决负权问题的修正算法，但1973年Johnson认为这些算法将为Ω(n2n)而不是O(n3)。这样一来，是否能在多项式时间内把Dijkstra算法推广到负权情形，成为了一个未解决的问题。本文在Ford、Edmonds和Karp等人工作的基础上，通过引入着色图，得到了一种计算复杂性为O(nm+n2logn)的算法，实现了把Dijkstra算法有效地推广到负权情形。
Bellman-Ford算法自1958年被提出以来，一直被公认为负权最短路问题最好的算法之一，它的最坏计算复杂性为O(mn)。2003年Meyer在点数为n、边数为O(n)、边的权服从一随机分布时，认为Bellman-Ford算法的平均复杂性为Ω(n4/3-η)，其中(0<η<1/3)。本文也对Bellman-Ford算法的平均复杂性进行了分析，得到了更一般的结果O(m√n)。
Bellman-Ford算法有两种改进算法，即第二改进算法和Yen的改进算法。本文第一次给出了这两种算法的平均复杂性，均为Ω(mlnn)。
关于负权最短路问题，本文得到了一种新算法，即算法1，该算法最坏计算复杂性为O(mn)，平均复杂性为O(mlnn)，在图为完全图、权服从0-1均匀分布的情况下平均复杂性可以降到惊人的O(m)。算法1取得了如下进展：
1.尽管在最坏计算复杂性上没有超过Bellman-Ford算法，在平均复杂性上超过了Bellman-Ford算法，且能够证明在任何情形下计算量都少于Bellman-Ford算法。其中Bellman-Ford算法的最坏计算复杂性为O(mn)，平均复杂性为O(m√n)。
2.尽管算法1在平均复杂性超过了Bellman-Ford算法，但相对于两个改进算法的平均复杂性优势不是太明显。为此，本文又进一步研究了算法1在图为完全图、权服从0-1均匀分布的情况下的平均复杂性，可以降到O(m)，从而进一步从平均复杂性方面超越了Bellman-Ford算法的两个改进算法。第二改进算法和Yen的改进算法的平均复杂性均为Ω(mlnn)。
3.算法1不仅能够从理论上证明优越于Bellman-Ford算法，而且能够从理论上证明优越于第二改进算法。但是，无法从理论上证明优越于Yen的改进算法。为此，本文对算法1进行了再改进，得到了算法2。算法2能够从理论上证明不仅优越于Bellman-Ford算法，而且优越于第二改进算法。算法2在平均情形下计算复杂性为O(mlnn)。
4.1998年Kolliopoulos和Stein在边服从大范围的随机分布时得到了一种平均复杂性为O(n2logn)的算法。既然算法1的平均复杂性为O(mlnn)，由于m≤n(n-1)，因而优于O(n2logn)，且是一个一般性的结果。
本文还给出了最短路问题在社会网络领域的一个重要应用，指出普遍流行的声望模型存在严重的理论缺陷且不具有普适性，为此给出了一个新的声望模型，并根据反向最短路问题的思想得到了反声望模型--影响力模型，同时发现影响力模型和著名的p-中值问题具有密切的联系，是推广了的p-中值问题。在计算声望模型和影响力模型时，应用了本文第三章提出的Dijkstra算法的改进算法，能够节约可观的计算量。