单源全部最短路问题实现论文.doc

单源全部最短路问题的实现

摘要：Dijkstra算法是公认的求图中最短路径的一个经典算法。使用该算法，我们可以在带权有向简单图中求出一个顶点到另一个顶点的最短距离及唯一一条最短路径，但不能计算出一个顶点到另一顶点的所有最短路径。本文通过分析Dijkstra算法缺陷形成的原因，设计了解决该问题的一种新算法——单源点全部最短路径算法（SS-ASP算法）。应用此算法，能高效地求出图中一个顶点到另一个顶点的最短距离及全部最短路径。本文对新算法进行了复杂度分析，并利用新算法进行了实例求解，最后给出了该算法的C语言源程序。
关键词：最短路径，全部最短路径，可能遗失的最短路径，遗失的最短路径， Dijkstra算法，单源点，关键点，直接前驱结点，链表数组，邻接矩阵，带权有向简单图

A Solution to the problem on All Shortest Paths of Single Source

Abstract : Dijkstra algorithm is a classical algorithm which can be used to solve the problem of the shortest path in graphs and is acknowledged by the public. We can work out the shortest distance as well as only one shortest path between one vertex and another in the Simple-Direction-weighting-Graph (SDWG)with the algorith,while not all of the shortest paths between the two vertex. a new kind of algorithm –the algorithm of All Shortest Pahts of Single Source(SS-ASP algorithm) ,has been designed by analysing the reason which causes the defect of Dijkstra algorithm in this thesis,which could solve this problem. Use this algorithm,the shortest distance and all of the shortest paths from one vertex to another can be figured out efficiently.In this paper, the complexity of the new algorithm has been analysed, and the new algorithm was applied to solve an instance , finally ,a correlative source program which is based C language was given.

Keywords: shortest path, all shortest paths, The possible missing shortest path,
missed shortest path, Dijkstra algorithm, single source, critical vertex, direct prior node, linked array, adjacency matrix, simple-weighting-graph

第一章 引言

1.1 本课题的研究意义
在电子导航、运输科学、城市规划、交通旅游、应急系统（如110报警、119火警、120急救等系统）以及电力、通讯等领域的生产实践过程中，最短路径算法起着举足轻重的作用；尤其是在地理信息系统（GIS）中，更是体现了它独特的魅力，该算法在各个科学领域中得到了广泛的应用。
最短路径不仅指地理意义上的距离最短，还可以引申到时间最少，费用最低等。但抽象起来，都归结于在包含N个顶点，E条边的带权有向简单图G=（V，E，W）中求指定两点之间的最短路问题。
目前，国内外一致公认的用于解决最短路径问题的优秀算法有Dijkstra算法和Floyd算法。前者是1959年由E.W.Dijkstra提出的用于解决单源点的最短路径问题的经典算法。但是，该算法亦存在着不足之处，即只能求解出一个顶点到其它各个顶点的一条最段路线，而不能计算出所有的最短路。但是，在某些生产实践领域，如交通系统的路径选择中，人们期望的是能找到所有最短路，以便满足各自的需求。因此，我们有必要对Dijkstra算法的缺陷进行分析和研究，并且找到较优的算法来弥补这个缺陷，将理论和实际相结合，为需要最短路问题的实践领域提供便利，达到满足人们某些日常生活需求的目的。

1.2 对Dijkstra算法的研究现状
目前提出的最短路径分析算法有很多种，主要集中在对D算法进行优化的工作上。有三种优化的算法效果比较好,它们分别是:TQQ（Graph Growth With Two Queues）,DKA(Dijkstra’s Algorithm Implemented With Approximate Buckets),以及DKD(Dijkstra’s Algorithm Implemented With Double Buckets)。其中TQQ算法的基础是图增长论,用两个FIFO队列实现了一个双端队列结构来支持搜索过程。后两种算法则是基于Dijkstra算法,采用桶结构，明显提高了永久标记点的搜索速度,但都是以空间换时间的做法。
虽然人们对D算法的优化做了大量的研究工作，并且根据具体的实际，改进D算法，使之高效率地应用到实践中去；但是对D算法缺陷的改进的研究工作可谓凤毛麟角。目前，国内外在此方面研究得比较多的是D算法的缺陷之一，即不能求带有负权的有向图的最短路径。故本课题值得探究。

第二章 Dijkstra算法及其缺陷

2.1 经典Dijkstra算法的内容
2.1.1 Dijkstra算法描述
假设一个带权有向图为G=（V，E，W）,其中V为顶点集，E为边的集合，W为边的权值。求从某一个顶点（假设为v）到其它各个顶点的最短路径的Dijkstra算法描述如下：
Dijkstra提出了一个按路径长度递增的次序产生最短路径的算法，首先引进一个辅助向量D，它的每个分量D[I]为弧上的权值，否则置D[i]为∞。显然，长度为D[j] = Min{D[i] | vi∈V}的路径就是从v出发的长度最短的一条最短路径。此路径为(v, vi)。
假设下一条长度次短的最短路径的终点是vk ，则可想而知，这条路径或者是(v, vk)，或者是(v, vj, vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。
一般情况下，假设S为已经求得最短路径的终点集合，则可证明：下一条最短路径(设其终点为x)或者是弧(v, x)，或者是中间只经过S中的顶点而最后到达顶点x的路径。这可用反证法来证明。假设此路径上有一个顶点不在S中，则说明存在一条终点不在S而长度比此路径短的路径。但是这是不可能的，因为我们是按路径长度递增的次序来产生各最短路径的，故此长度比此路径短的所有路径均已产生，它们的终点必定在S中，即假设不成立。因此在一般情况下，下一条长度次短的最短路径的长度必是D[j] = Min{D[i] |vi∈V-S }。其中，D[i]或者是弧(v, vi)上的权值，或者是D[k](vk∈S)和上的权值之和。
2.1.2 Dijkstra算法的具体步骤
(1)假设用带权邻接矩阵cost来表示带权有向图,cost[i][j]表示弧<Vi,Vj>上的权值(i≠j,否则cost[i,j]= ∞)。若<Vi,Vj>不存在,则置cost[i][j]为∞(计算机上可允许的最大值)。S为已找到从Ｖ出发的最短路径的顶点集合,其初始状态为空集。那么,从V1出发到其余各顶点Vi可能达到的最短路径长度初始值D[i]= cost[LocateVex(G,v)][i],vi∈V ，LocateVex(G,v)表示v在图G中的序号(2)选择Vj,使得D[j]=min{D[i]｜Vi∈V-S},那么Vj就是当前求得的一条从Ｖ1出发到达Vj的最短路径的终点，令S=S∪{j}。(3)修改从v出发到集合V-S上任一顶点Vk可达到的最短路径长度。如果D[k]>D[j]+ D[j][k]则修改D[k]为D[k]= D[j]+ D[j][k]。(4)重复操作(2),(3)共ｎ-1次,由此求得从v到图上其余各顶点的最短路径长度是不减的序列。

2.2 经典Dijkstra算法的MATLAB程序实现
通过功能强大的数学工程软件Matlab6.0,我们编出了Dijkstra算法的Matlab程序，详细情况请参考附录2。

2.3 经典Dijkstra算法的缺陷
我们首先给出一个实例，用Dijkstra算法进行求解，然后从中找出Dijkstra算法的缺陷所在。
某一带权有向图G如图1所示，其带权邻接矩阵如图2所示，下面用Dijkstra算法求从v1到其余各个顶点的最短路径，其运算过程以及D变量的变化如表1所示。

v6

100 60
v1
v5
30 ∞ 5 10 50 30 100
∞ ∞ 5 ∞ ∞ ∞
5 50 10 20 ∞ ∞ ∞ 50 ∞ 50
v4
10 50 ∞ ∞ ∞ ∞ ∞ 10
v2
v ∞ ∞ ∞ 20 ∞ 60
5 ∞ ∞ ∞ ∞ ∞ ∞
v3
50

图1 带权有向图G 图2 图G的邻接矩阵表示

由表1我们可以得到v1到其余各个顶点的最短路径如下表2所示：
顶点（VER）
最短路径（SP）
最短路径长度（D[i]）
v2
v1 v2
5
v3
v1 v3
10
v4
v1 v5
50
v5
v1 v4
30
v6
v1 v3 v6
60

表2 图G中，v1到其余各个顶点的最短路径以及长度

表1 有向图G中，v1到其它各顶点最短路径的Dijkstra算法求解过程

终点
从v1到各终点的D值与最短路径求解过程
第一趟
第二趟
第三趟
第四趟
第五趟
v2
5
(v1,v2)
——
——
——
——
v3
10 (v1,v3)
10
(v1,v3)
——
——
——
v4
50 (v1,v4)
50
(v1,v4)
50
(v1,v4)
50
(v1,v4)
——
v5
30
(v1,v5)
30
(v1,v5)
30
(v1,v5)
——
——
v6
100
(v1,v6)
100
(v1,v6)
60
(v1,v3,v6)
60
(v1,v3,v6)
60
(v1,v3,v6)
vj
v2
v3
v5
v4
v6

S

{v1,v2}
{ v1,v2,
v3}
{ v1,v2,
v3,v5}
{ v1,v2,
v3,v5,v4}
{ v1,v2,v3,
v5,v4,v6}

path

v1 v2

v1 v3

v1 v5

v1 v4
v1 v3
v6

经过上面的步骤，我们用Dijkstra算法求出了带权有向图G中，从v1到其余各个顶点的最短路径及其长度。但是，我们仔细观察便可以发现如下的事实：v1到v3的最短路径其实还有一条，便是v1 v2 v3，其距离是10；v1到v4的最短路径也存在另外的一条最短路径，即v1 v5 v4，其距离为50；v1到v6还存在距离为60的另外三条最短路径，分别是：v1 v2 v3 v6，
v1 v4 v6，v1 v5 v4 v6。由此可见，用Dijkstra算法的缺陷在于，求单源点的最短路径时，会遗失某些最短路径。当图中存在一顶点到另外一个顶点的多条最短路径时，Dijkstra算法只能求出其中的一条，而丢失其它存在的最短路径。

2.4 经典Dijkstra算法缺陷原因分析
2.3.1 构造Dijkstra算法缺陷原因分析表
通过上面的例子，我们发现了经典Dijkstra算法的一个缺陷——不能计算出带权有向图一顶点到其它顶点的所有最短路径。那么使用Dijkstra算法时，为什么会造成最短路径的丢失呢？通过详细分析D算法的每一个计算过程，得到了D算法求单源最短路径的缺陷分析表，如表3所示，从中可以找到问题的答案。

表3 Dijkstra算法缺陷原因分析表

第一趟
第二趟
第三趟
第四趟
第五趟
D[i]
L
R
M
D[i]
L
R
M
D[i]
L
R
M
D[i]
L
R
M
D[i]
L
R
M
V2
5
(v1,
v2)
_
_
_

_
_
_
_

_
_
_
_
_
_
_
_
_
_
_
_

V3

10
(v1,
v3)
10
(v1,
v2,
v3)

=

_

10
(v1,
v3)
_
_
_

_

_

_

_
_
_
_
_
_
_
_
_

V4

50
(v1,
v4)

∞
<

_

50
(v1,
v4)
60
(v1,
v3,
v4)

<

_

50
(v1,
v4)
50
(v1,
v5,
v4)

=
_

50
(v1,
v4)
_
_
_
_
_
_
_
V5
30
(v1,
v5)

∞
<
_
30
(v1,
v5)
∞
<
_
30
(v1,
v5)
_
_
_
_
_
_
_
_
_
_
_

V6

100
(v1,
v6)

∞
<

_

100
(v1,
v6)
60
(v1,
v3,
v6)

>
D[6]
=
60

60
(v1,
v3,
v6)
90
(v1,
v5,
v6)

<
_

60
(v1,
v3,
v6)

60
(v1,
v4,
v6)
=
_

60
(v1,
v3,
v6)

_

_

_
Vj
v2
v3
v5
v4
v6
S
{v1,v2}
{ v1,v2,v3}
{ v1,v2,v3,v5}
{ v1,v2,v3,v5,v4}
{ v1,v2,v3,v5,v4,v6}
SP
v1 v2
v1 v3
v1 v5
v1 v4
v1 v3 v6
PMP
①v1 v2 v3

②v1 v2
v3 v6
③v1 v5 v4

④v1 v4 v6
⑤v1 v5
v4 v6
____

MP
____

①v1 v2 v3

____

③v1 v5 v4

②v1 v2
v3 v6
④v1 v4 v6
⑤v1 v5
v4 v6
DP[u]
DP[3]={v2}
DP[6]={v3}
DP[4]={v5}
DP[6]={v4}
——

2.3.2缺陷原因分析表符号说明
下面对缺陷原因分析表中的各项符号进行说明。
①D[i]项:最短路径长度项。表示当前已经求出的从v1到顶点vi(2≦k≦n)的最短路径长度。初始值为D[i]=cost[1][i]。
②L项：长度项。L=D[j]+cost[j][u]，其中u是顶点vu的序号，而且vu∈V-S，表示每趟求出vj之后，计算从v1出发，经过vj，到达vu的路径长度。
③R项(relationship):关系项。表示D[u](vu∈V-S)与L大小关系的比较，有三种，大于(>)、小于(<)、等于(=)。
④M项(modify):修改项。表示修改D[u]值(vu∈V-S)。
若D[u]>L=D[j]+cost[j][u]时，则修改D[u]=L，否则D[u]值保持不变。
⑤vj项：关键结点。表示某一趟中，满足D[j]=min{D[i]｜Vi∈V-S}的顶点vj。它表示已经求出的从v1到vj的最短路径的终点。
⑥S项：已求顶点集。表示每一趟中，满足D[j]=min{D[i]｜Vi∈V-S}的顶点vj的集合，表示已经求出了从v1到其本身的最短路径的顶点。
⑦SP项：最短路径(shortest path)。记录已经求出的从v1到其余各顶点的最短路径。
⑧PMP项：可能遗失的最短路径(possible missing shortest path)。每趟求解确定vj之后，我们要计算源点v1出发，经过vj到达其余各个顶点vu(vu∈V-S)的路径长度L=D[j]+cost[j][u]，如果有D[u]=L，那么说明由v1到达vj的每一条路径，再添加一个终点vu，都是源点v1到达顶点vj的可能的最短路径。原因是D[u]表示v1到顶点vu(vu∈V-S)的当前最短路径长度，而L的值与其相等，故都是可能的最短路径。只有在某一趟的计算过程中，确定D[u]就是v1到vj的最短路径长度时，我们才可以确定经过vj到达vu的路径也都是v1到vj的最短路径。
⑨MP项：丢失的最短路径项(missed shortest path)。在D算法的第i趟计算中，若存在v1 … vj vu的PMP项，但在第j趟计算中，确定v1到vu的最短路径长度为D[u]，那么称所有的v1 … vj vu的PMP项为MP项。
⑩DP[u]项：vu(vu∈V-S)的直接前驱结点集(Direct prior node)。DP[u]集中顶点元素的构成要满足如下条件：
DP[u]={vj｜D[u]=D[j]+cost[j][u]，vj∈min{D[i]｜Vi∈V-S}, vu∈V-S }，表示从v1出发，经过vj到vu的所有PMP路的关键点vj的集合，它是vu的直接前驱结点。并且将满足上述条件的关键点vj称为直接前驱关键点。

2.3.3 Dijkstra算法缺陷的原因分析
从表3的MP项中我们可以看出，整个D算法过程中，丢失了5条最短路径。究竟原因何在？下面我们就表3中的PMP项，以及MP项的产生过程进行具体分析，来阐明D算法缺陷的原因。
首先，在第一趟计算中，根据D算法，我们可以得到v1到v2的最短路径及其长度，同时，我们可以求得从v1出发，经过v2到达v3的路径长度，和当前v1到v3的最短路径长度D[3](v3∈V-S)相等，两者的值均为10所以，
v1 v2 v3也应该是当前v1到v3的最短路径.但是D算法没有给出其路径，故称之为可能遗失的最短路径(PMP)。在第二趟计算中，根据D算法我们选择了vj=v3，求得v1到v3的最短路径长度为D[3]=10，于是我们可以断定，
v1 v2 v3也是v1到v3的最短路径。但是D算法求得的v1到v3的最短路径只有v1 v3这一条，而遗失了v1 v2 v3这条路径，故称之为MP。 同理，按照上面的方法，我们可以在第二趟中求出v1到v6的一条PMP路，为
v1 v2 v3 v6，其长度为60。同时在第五趟中，可以确定v1到v6的最短路径长度为D[6]=60，所以，可以断定此PMP路为MP路，是一条被丢失的从v1到v6的最短路径。
按照上面的方法，我们同样可以得到另外的从v1到v4的一条PM路③，和两条从v1出发经过v4到达v6的两条PM路④与⑤。
综上所述，我们可以发现传统D算法缺陷的根本原因就在于第三步对于D[u](vu∈V-S)值的修改过程。经典D算法只考虑了当D[u]>L=D[j]+cost[j][u]时，则修改D[u]=L，而忽略了两者相等的情况，即当D[u]=D[j]+cost[j][u]时，
该做如何处理。正是因为没有考虑这个情况，所以造成了最短路径的丢失。
2.4 弥补经典Dijkstra算法缺陷的关键技术
经过2.3对D算法缺陷原因的具体分析，我们发现了其根本原因所在。根据2.3.3的内容我们可以知道，要弥补D算法遗失可能最短路径的这个缺陷，关键技术在于修改D算法的第三步，使之具有计算并存储每一趟的PMP路的功能。修改的具体操作为(1)若D[u]=D[j]+cost[j][u]时，保存从v1出发经过vj到达vu的所有PMP路；(2)若D[u]>L=D[j]+cost[j][u]时，则修改D[u]=L，同时销毁当前存储的v1到vu的所有可能最短路径，并将v1 … vj vu的所有PMP路保存。
为此，我们必须改进传统D算法的存储结构和算法内容，形成另外一种可以求出单源点的全部最短路径及最短路长度的新算法，定义为单源全部最短路径算法，即SS-ASP(All Shortest Paths of Single Source)算法。
第三章 单源点的全部最短路径算法（SS-ASP算法）

3.1 SS-ASP算法的存储结构
在第二章中我们分析了D算法的一个缺陷——遗失可能最短路径的原因，并且给出了解决这个问题的关键技术，根据关键技术的思想，我们设计了一个新的改进算法—SS-ASP算法，解决一个顶点到其余各个顶点的全部最短路径问题。
在2.4中我们提到了根据关键技术的要求，必须对传统D算法的存储结构进行修改，下面将详细讨论SS-ASP算法的具体存储结构。
我们假设一个带权有向图为G，G=(V,E,W),其中V为顶点集，E为边集，W为边的权值，G中的顶点数设为n，且图G为简单图(无环和无重边)。SS-ASP算法的存储结构如下：
(1)图G的存储结构：用邻接矩阵cost来存储。当i≠j时，cost[i][j]=w表示顶点vi到顶点vj的权值为w；若vi到vj不存在有向边，则cost[i][j]= ∞。若i=j，则cost[i][j]= ∞。
(2)最短路径长度的存储：用一维数组D来存储。D[i]表示存放从v1到顶点vi(2≤i≤n)的当前可能最短距离。一旦在某一趟计算中，v1到顶点vi的最短路径长度已经求得，那么D[i]就是从v1到vi的最短路径长度。
(3)直接前驱结点集的存储：用结构体数组DP[u]来存储vu(vu∈V-S)的直接前驱关键点vj。其C语言的定义如下：
Struct DPT //define direct prior talbe
{ Char VP[MAXSIZE];//prior vertex list,存放直接前驱结点
int num; //记录当前前驱结点的数量
}DP[Max-Vertex-Num];//DP的长度最大值为图中顶点数最大值
初始化时，置DP[1].VP[1]=NULL，DP[1].num=0；
置，DP[k].num=1；
(4)所有最短路径的存储：用链表数组ASP来存放已经求得的从v1到顶点vj(2≤j≤n)的所有最短路径的顶点序列。ASP表由一个一维数组ASP[m]和若干个子表ASP1j(2≤j≤n)组成。
①一维数组ASP[m](1≤m≤n)：用于存放各个子表ASP1j的起始地址，初始化时，置ASP[1]=NULL。
V Vnext
②子表ASP1j：用于存储v1到vj的所有最短路径,假设共有h条。它由一个一维数组ASP1j[k](1≤k≤h)和若干单链表组成。其中一维数组ASP1j[k]中存放单链表的头指针；单链表的每个结点结构为如又所示：
其中V为顶点域，Vnext为路径指针域，指向此路径单链表的下一个顶点。

ASP表的逻辑存储结构如下图3所示：

V
Vnext
……
ASP[m] ASP1j[k]
1

2
ASP12
3
ASP13
…
…
j
ASP1j
…
…
n
ASP1n
1
2
…
h
v1

vi

v2
∧

v1

vi

v2
∧
……

v1

vi

v2
∧
……

……

1
2
…
h
v1

vi

v2
∧

v1

vi

……

v2
∧

v1

vi

v2
∧
……

图3 ASP表存储结构图

3.2 SS-ASP算法的基本思想
每一趟计算过程中，求出v1到vj的最短路径长度D[j]之后，便比较D[u](vu∈V-S)与L(L=D[j]+cost[j][u])的大小关系。若D[u]=L，则将vj存储到vu的直接前驱表DP[u]中；若D[u]>L，则先删除DP[u]中所有的直接前驱关键点，再将vj添加到DP[u]中，然后再修改D[u]的值为D[u]=L；否则DP[u]和D[u]不做任何更改。
完成上述步骤后，我们便可以利用DP表和ASP表产生v1到vj的所有最短路径表ASP1j表。其方法是:依次扫描DP[j]数组中的每一个直接前驱关键点，设为vp(1≤p≤n,p≠j)。(1)若vp=v1，则直接在ASP1j表中生成一条v1到vj的具有两个结点的路径单链表；(2)若vp≠v1，则将ASP1p表中的每一个路径单链表拷贝到ASP1j表中，并且在每一条链路的尾结点后插入一个新的结点vj，从而形成v1到vj的所有最短路径表，即ASP1j表。这是因为，若DP[j]中的某一个直接前驱关键点是vp，则ASP1p链表中存储的所有链路是已经求出的从v1到vp的所有最短路径。

3.3 SS-ASP算法的具体步骤
根据3.2中提出的算法的基本思想，我们设计SS-ASP算法的详细步骤如下：
第一步：初始化。(1)令S={v1}，Sn=1；其中Sn表示S集中的顶点个数。(2)置D[i]=cost[1][i]，其中vi∈V-S；(3)若i=1，则置DP[i].VP[1]=∧，DP[i].num=0；否则，当2≤i≤n时，若cost[1][i]≠∞，则置DP[i].VP[1]=v1，DP[i].num=1；若cost[1][i]=∞，则置DP[i].VP[1]= ∧，DP[i].num=0。
第二步：求D[j]。选择vj，使之满足条件D[j]=min{ D[i]｜vi∈V-S }，并且令S=S∪{j}。
第三步：修改DP[u]表及D[u]的值 (其中vu∈V-S)。
(1) if (D[u]==D[j]+cost[j][u]) DP[u].VP[num++]=vj；
(2) else if (D[u]>D[j]+cost[j][u])
for(k=1;k<=DP[u].num;k++) DP[u].VP[i]=NULL;
DP[u].VP[1]=vj; D[u]=D[j]+D[j][u]
第四步：产生从v1到vj的所有最短路径表ASP1j，方法如下：
依次扫描DP[j]数组中的每一个直接前驱关键点，设为vp(1≤p≤n,p≠j)。
(1)若vp=v1，则直接在ASP1j表中生成一条v1到vj的具有两个结点的路径单链表；(2)若vp≠v1，则将ASP1p表中的每一个路径单链表拷贝到ASP1j表中，并且在每一条链路的尾结点后插入一个新的结点vj，从而形成v1到vj的所有最短路径表，即ASP1j表。
第五步：判断S中顶点的个数是否为n，if(Sn==n)程序结束，否则转步骤二。

3.4 SS-ASP算法的程序流程图

根据算法步骤，我们可以作出SS-ASP算法的程序流程图，如图4所示。

3.5 SS-ASP算法的程序实现

由算法及流程图，我们选择C语言，编写了实现SS-ASP算法的源程序，通过计算机编译测试，验证了该算法和程序的正确性。具体源程序请参考附录1。

初始化操作
求D[j]
if（D[u]= =L）
if（D[u]>L）
DP[u].VP[num++]=vj
删除DP[u]中的所有直接前驱结点,将vj保存，修改D[u]
扫描DP[j]中的直接前驱关键点，设为vp
if（vp= =v1）
产生v1到vj的最短路径表，即ASP1j链表。
判断DP[j]表是否扫描完毕
if（Sn= =n）
打印结果，程序结束
直接在ASP1j中增加v1到vj的链路
图4 SS-ASP算法流程图

Y

N

Y

N

Y

N

N

Y

N

Y

第四章 SS-ASP算法分析

4.1空间复杂度分析
由于采用邻接矩阵cost来存储图G，所以，算法的空间复杂度为。
4.2时间复杂度分析
(1)第一步的时间复杂度为T(n)=O(n)；(2)第二步的时间复杂度为，因为。
(3)第三步所花时间是用于修改DP表和D[u]值。假设第i(1≤i≤n-1)次从集合V-S中选取满足条件D[j]=min{ D[i]｜vi∈V-S } 的顶点vj放入集合S后，此时集合中共有i+1个顶点（包含顶点v1），那么在DP表中，这i+1个顶点的DP数组不需再修改，设vu为不属于这i+1个顶点中的任意一个顶点，则DP表中需要修改的DP[u]数组最多为n-i-1个，而此时要修改的每个DP[u]表中最多有i个结点。分如下两种情况来修改一个DP[u]数组：
①仅插入一个结点到数组中，显然时间复杂度为O(1)；
②删除DP[u]中原来所有的直接前驱关键结点后，再添加一个新的结点，时间复杂度为O(i+1)。由此可知，第i次从集合中取一个距离最小的顶点放入集合S后，仅修改DP数组中一个前趋单链表的最坏时间复杂度为O(i+1)，要修改整个DP数组的最坏时间复杂度为：O((n-i-1)*(i+1))。故在整个算法运行过程中，第三步最坏的时间复杂度为T(n)=,且
=。修改D[u]的时间复杂度为，
即。
综上，第三步最坏时间复杂度为。

(4)第四步是产生从v1到vj的所有最短路径。设一个顶点数为n的带权有向图G中,存在这样一个性质，即从一个顶点到另一个顶点的所有最短路径总数的数量级最多为O(sh(n)) 。(sh(x)=((ex-e-x)/2))。设第四步时在DP表中查得vj顶点的一个直接前趋为vp(1≤p≤n)，在ASP1p表中,从v1到vp的所有路径单链表总条数最多为O(sh(n))，因为一条路径单链表最多含n个结点，因此，每扫描或产生一条路径单链表时间复杂度为O(n)，在第四步中依次扫描APS1p表中所有路径单链表，并在ASP1j表中产生对应的路径单链表的最坏时间复杂度为O(n*sh(n)+n*sh(n))，即O(n*sh(n))。
因为每个顶点vj在第四步时所有直接前趋vp最多有n-1个，因此产生ASP1j表的最坏时间复杂度为：O((n-1)*n*sh(n))，即。而在整个SS-ASP算法中这样的顶点有个n-1个，(因为不包括源点)。因此第四步总的最坏时间复杂度为。
(5)第五步最坏时间复杂度为O(n)。 综上所述，整个算法的最坏时间复杂度为,即。
虽然，sh(n)在最坏情况下是指数函数，但这不能作为否定该算法的依据，因为它是一个带权有向图的固有属性。根据上面的性质，从源点v1至其余n-1个顶点所有最短路径的总数目的数量级为O((n-1)*sh(n)),即O(nsh(n))；而一条最短路径上所含结点总个数的数量级为O(n)，因此任何一个求图中一个顶点到其它各顶点的所有最短路径的算法其时间复杂度应不小于O(n*(n-1)*sh(n))，即，这是此类求所有最短路径算法时间复杂度的一个下限值，而该算法时间复杂度仅为,但是≈，故SS-ASP算法时间复杂度非常接近于任何一个求所有最短路径算法的时间复杂度的一个下限值，因此该算法无疑是一种高效的算法。

第五章 SS-ASP算法应用
5.1 SS-ASP算法的实例手工求解
5.1.1 实例详细计算过程
给出图G中，单源点v1到其它各顶点的计算过程，如下表4所示

第一趟
第二趟
第三趟
第四趟
第五趟
D[i]
L
R
M
D[i]
L
R
M
D[i]
L
R
M
D[i]
L
R
M
D[i]
L
R
M
V2
5
(v1,
v2)
_
_
_

_
_
_
_

_
_
_
_
_
_
_
_
_
_
_
_

V3

10
(v1,
v3)
10
(v1,
v2,
v3)

=

_

10
(v1,
v3)
_
_
_

_

_

_

_
_
_
_
_
_
_
_
_

V4

50
(v1,
v4)

∞
<

_

50
(v1,
v4)
60
(v1,
v3,
v4)

<

_

50
(v1,
v4)
50
(v1,
v5,
v4)

=
_

50
(v1,
v4)
_
_
_
_
_
_
_
V5
30
(v1,
v5)

∞
<
_
30
(v1,
v5)
∞
<
_
30
(v1,
v5)
_
_
_
_
_
_
_
_
_
_
_

V6

100
(v1,
v6)

∞
<

_

100
(v1,
v6)
60
(v1,
v3,
v6)

>
D[6]
=
60

60
(v1,
v3,
v6)
90
(v1,
v5,
v6)

<
_

60
(v1,
v3,
v6)

60
(v1,
v4,
v6)
=
_

60
(v1,
v3,
v6)

_

_

_
Vj
v2
v3
v5
v4
v6
S
{v1,v2}
{ v1,v2,v3}
{ v1,v2,v3