论文部分内容阅读
摘要：迪杰斯特拉算法是图论中计算最短路径的经典算法，但在实际使用中该算法耗费大量的计算时间和存储空间。通过对传统迪杰斯特拉算法的深入分析，在计算时间和存储空间上对该算法提出了一种新的优化方案，并给出了优化后的详细算法。改进算法从消除冗余计算和冗余存储入手，采用链表数组作为存储结构。经算法复杂度分析，优化后的迪杰斯特拉算法在求解最短路径问题时在时间和空间复杂度上都有明显的提高。该优化算法操作性强，具有一定的实用价值。
关键词：最短路径；迪杰斯特拉算法；优化研究；链表
中图分类号：TP312文献标识码：A文章编号：1009-3044(2008)26-1702-02
Optimization Research for Dijkstra Algorithm Based on Linked List
ZHANG Hong-ke
(Tongji University,Shanghai 200122,China)
Abstract:Dijkstra algorithm is a classic algorithm for computing the shortest path, but it uses lots of time and memories in practice. On the basis of analyzing Dijkstra algorithm thoroughly, it shows a new optimal solution to the problem, and gives the detail algorithm. The improved algorithm can avoid redundant computing and storage, and uses linked list array as storage structure. The time complexity and space complexity of the algorithm are improved markedly in computing the shortest path. The improved algorithm with strong maneuverability could have important applications.
Key words: shortest path; dijkstra algorithm; optimization study; linked list
1 引言
在現实生活工作中，很多问题都与寻找一个图的最短路径密切相关，如交通路线的选择、城市地下管道的布局、网络线路的铺设等问题。这里的最短路径不仅仅指地理意义上的距离最短，还可引申为最少费用、最短时间、吞吐量最大等约束条件。迪杰斯特拉算法于1959年由E.W .Dijkstra提出，是图论中求最短路径的一个著名的算法，使用其可以求得图中一点到其他各顶点的最短路径。其中以先求得最短路径树著称。但在实际应用中，使用该算法会耗费大量的计算时间和存储空间。虽然有很多人对迪杰斯特拉算法提出了一些优化算法，但都达不到最理想的结果。针对这个问题，本文将基于迪杰斯特拉算法基本思想，在计算时间和存储空间上对其进行优化，使得迪杰斯特拉算法在求解最短路径问题时达到时间的下限。
2 传统迪杰斯特拉算法的主要思想
最短路径问题是指在一个带权值的图中找出两个指定节点间的一条权值和最小的路径。而迪杰斯特拉算法是经典的解决最短路径问题的算法，它可以找出指定节点到其他各个节点间的最短路径，其主要思想是首先从源点求出长度最短的一条路径，然后通过对路径长度迭代得到从源点到其他各目标节点的最短路径。
在具体计算中，我们引入一个辅助向量D，它的每一个分量D[i]初值为弧上的权值。若v到vi没有边，则置D[i]为∞。显然，从v出发的长度最短的一条最短路径就是长度为D[j]＝min｛D[j] | vi∈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) 加vi到vk的弧上的权值。
3 对存储结构进行优化
设G=(V，E)是一个带权的有向图，其中V为顶点的集合，E为边的集合。G 中顶点数为n。下面使用改进算法来求从V0（源点）到其他各顶点的最短路径长度和最短路径经过的顶点，其存储结构如下：
设有向图G=(V，E)，以邻接矩阵作为存储结构，用链表数组MGraph来存储该矩阵G。将邻接矩阵的每一行用一个单链表来表示，链表中的元素不为∞，每一个顶点有两个元素，一个以所在邻接矩阵列号作为顶点识别号码，一个为该点的权值。其C 核心代码如下:
typedef struct
{int row,vol;
MNode *next;
} MNode;
class MGraph
{public:
MGraph () {current=NULL;first=current;}
MNode *first,*current;
MNode *GotoFirst () {if (first) {current=first;return current;} else return NULL;}
void SetFirst (MNode *p) {first=p;current=first;}
void Add (MNode *p) {current- >next=p;current=p;}
MNode *Next ( ) { if ( current - >next) { currrent=current- >next;return current;} else return NULL;}
另设一维数组D来存储各顶点到V0的最短距离，同时设一维数组P来存储前驱顶点。引入一个辅助双向链表来存储正在参与比较计算的顶点，使用双向链表在删除顶点时可以降低算法的时间复杂度。其C 核心代码如下：
typedef struct
{int row;
CNode *next, *prev;
}
CNode;
class Path
{public:
Path () {n=;current=NULL;first=NULL;}
int n;
CNode *first, *current;
void SetFirst ( CNode* p) {first=p;current=first;n=1;}
CNode* First () {if (first) current=first;else current=NULL;return current;}
void AddRear (CNode *p) {current-＞next=p;p-＞prev=current;current=p:n ;}
int Delete (CNode *p);
CNode *Next () {if (current-＞next) {current=current-＞next;return current;} else return NULL;}
bool IsEmpty () {return n=0;}}
4 经优化后的算法
通常在实际应用中，邻接矩阵大多为稀疏矩阵，导致在计算过程中有大量∞参与运算。这就降低了算法的效率，所以改进算法将从消除冗余计算和冗余存储入手。
下面用链表数组MGraph G[n]来表示邻接矩阵，算法步骤如下：
1) 用与v0直接相连的顶点的权值对D[vi]进行初始化，其他设置为机器所允许的最大值。
2) 把与v0直接相连的顶点添加到链表Path中。
3) 在Path中找到权值最小的顶点w，并从中删除该顶点，如无剩余顶点则结束。
4) 在G里与w直接相连的其余各个顶点vi的权值中比较D[vi] s(w，vi)的大小，如果D[vi]小于D[vi] s(w，vi)，且如果D[vi]为∞则将vi添加到Path中，然后将P[vi]的前驱设置为w，并修改最短路径D[vi]= D[w] s(w，vi) 。以此重复步骤(2)。
下面给出改进后算法的C 核心源代码：
bool OptForDijkstra (MGraph *G,int v,int *p,int *D,int n)
{int w,i,min;
Path ph;
MNode *pnode;
CNode *cn1,*cn2;
if (v0＜1||v0＞n) return false;
for (i=0;i＜n;i ) {D[i]=INFINITY;p[i]=-1;}
pnode=G[v0].first;
while (pnode!=NULL)
{D[pnode-＞row]=pnode-＞vol;
CNode *l=newNode( );
l-＞row=pnode-＞row;
p[pnode-＞row]=v0;
ph.AddRear(l);
Pnode=pnode-＞next;}
while (!ph.IsEmpty( ))
{min=INFINITY;
cn2=ph.First( ) ;
while (cn2)
{if (D[cn2- ＞row]＜min)
{cn1=cn2;
w=cn1-＞row;
min=D[w];}
cn2=ph.Next( );
ph.Delete(cn1);
Pnode=G[w].first;
while ( pnode)
{if (D[pnode-＞row]＞(min pnode-＞vol))
{if (D[pnode- ＞row] ==INFINITY)（下轉第1734页）
（上接第1703页）
{CNode *pNode=newChainNode ( ) ;
pNode- ＞row=pnode- ＞row;
ph.AddRear (pNode ) ;}
D [pnode- ＞row] =min pnode- ＞vol;
P [pnode- ＞row] =w;}
pnode=pnode- ＞next;}}
return true;}}
5 算法复杂度分析
1) 时间复杂度：
我们分析这个优化后算法的运行时间。显然，步骤1的时间复杂度为o(n)，步骤2的时间复杂度为o(n)。而对于步骤3，第一次循环的次数等于与V0 直接相连的顶点数n1，第二次循环的次数为n1-1再加上与第一次找到的顶点直接相连并且与V0 的距离为无穷大的顶点的个数。依次类推，直到ph中顶点个数为0为止。最坏情况下如果V0与其余各顶点都有直接相连，则每次循环的次数为(n-1)，(n-2)，…1，那么时间复杂度为(n- 1) (n-2) … 1,即为o(n^2 )。观察步骤4，对于任何最短路径算法都至少对每条边检查一次，因为任何一条边都有可能在最短路径中，因此步骤4 的时间复杂度为o(T)，当T=n^2 时，复杂度为o(n^2)，此时和迪杰斯特拉的算法相同。
所以，经过优化算法的最坏时间复杂度为max{o(n)，o( T )，o(n^2 )}，即为o(n^2 )。
2) 空间复杂度：
优化后的算法采用链表数组作为存储结构，有效地消除了大量的冗余存储，因此空间复杂度为o(T),这里T为有向图的边数。在最差情况下即T=n^2时,算法的空间复杂度为o(n^2)。
6 结束语
经实际测试分析，当T＜＜n 时，即在稀疏图的情况下，这个改进的算法非常有用，有效地消除了大量的冗余计算和冗余存储，使得该算法的时间复杂度和空间复杂度都有优于经典的迪杰斯特拉算法。本优化算法操作性强，具有一定的实用价值。
参考文献：
[1] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997.
[2] 李春葆.数据结构考研指导[M].北京:清华大学出版社,2003.
[3] Bondy J A,Murty U S R.图论及其应用[M].北京:科学出版社,1984.
[4] Cormen T H,Charles E L,Ronald L R, et al.算法导论[M].2版,影印版.北京:高等教育出版社,2002.
关键词：最短路径；迪杰斯特拉算法；优化研究；链表
中图分类号：TP312文献标识码：A文章编号：1009-3044(2008)26-1702-02
Optimization Research for Dijkstra Algorithm Based on Linked List
ZHANG Hong-ke
(Tongji University,Shanghai 200122,China)
Abstract:Dijkstra algorithm is a classic algorithm for computing the shortest path, but it uses lots of time and memories in practice. On the basis of analyzing Dijkstra algorithm thoroughly, it shows a new optimal solution to the problem, and gives the detail algorithm. The improved algorithm can avoid redundant computing and storage, and uses linked list array as storage structure. The time complexity and space complexity of the algorithm are improved markedly in computing the shortest path. The improved algorithm with strong maneuverability could have important applications.
Key words: shortest path; dijkstra algorithm; optimization study; linked list
1 引言
在現实生活工作中，很多问题都与寻找一个图的最短路径密切相关，如交通路线的选择、城市地下管道的布局、网络线路的铺设等问题。这里的最短路径不仅仅指地理意义上的距离最短，还可引申为最少费用、最短时间、吞吐量最大等约束条件。迪杰斯特拉算法于1959年由E.W .Dijkstra提出，是图论中求最短路径的一个著名的算法，使用其可以求得图中一点到其他各顶点的最短路径。其中以先求得最短路径树著称。但在实际应用中，使用该算法会耗费大量的计算时间和存储空间。虽然有很多人对迪杰斯特拉算法提出了一些优化算法，但都达不到最理想的结果。针对这个问题，本文将基于迪杰斯特拉算法基本思想，在计算时间和存储空间上对其进行优化，使得迪杰斯特拉算法在求解最短路径问题时达到时间的下限。
2 传统迪杰斯特拉算法的主要思想
最短路径问题是指在一个带权值的图中找出两个指定节点间的一条权值和最小的路径。而迪杰斯特拉算法是经典的解决最短路径问题的算法，它可以找出指定节点到其他各个节点间的最短路径，其主要思想是首先从源点求出长度最短的一条路径，然后通过对路径长度迭代得到从源点到其他各目标节点的最短路径。
在具体计算中，我们引入一个辅助向量D，它的每一个分量D[i]初值为弧上的权值。若v到vi没有边，则置D[i]为∞。显然，从v出发的长度最短的一条最短路径就是长度为D[j]＝min｛D[j] | vi∈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) 加vi到vk的弧上的权值。
3 对存储结构进行优化
设G=(V，E)是一个带权的有向图，其中V为顶点的集合，E为边的集合。G 中顶点数为n。下面使用改进算法来求从V0（源点）到其他各顶点的最短路径长度和最短路径经过的顶点，其存储结构如下：
设有向图G=(V，E)，以邻接矩阵作为存储结构，用链表数组MGraph来存储该矩阵G。将邻接矩阵的每一行用一个单链表来表示，链表中的元素不为∞，每一个顶点有两个元素，一个以所在邻接矩阵列号作为顶点识别号码，一个为该点的权值。其C 核心代码如下:
typedef struct
{int row,vol;
MNode *next;
} MNode;
class MGraph
{public:
MGraph () {current=NULL;first=current;}
MNode *first,*current;
MNode *GotoFirst () {if (first) {current=first;return current;} else return NULL;}
void SetFirst (MNode *p) {first=p;current=first;}
void Add (MNode *p) {current- >next=p;current=p;}
MNode *Next ( ) { if ( current - >next) { currrent=current- >next;return current;} else return NULL;}
另设一维数组D来存储各顶点到V0的最短距离，同时设一维数组P来存储前驱顶点。引入一个辅助双向链表来存储正在参与比较计算的顶点，使用双向链表在删除顶点时可以降低算法的时间复杂度。其C 核心代码如下：
typedef struct
{int row;
CNode *next, *prev;
}
CNode;
class Path
{public:
Path () {n=;current=NULL;first=NULL;}
int n;
CNode *first, *current;
void SetFirst ( CNode* p) {first=p;current=first;n=1;}
CNode* First () {if (first) current=first;else current=NULL;return current;}
void AddRear (CNode *p) {current-＞next=p;p-＞prev=current;current=p:n ;}
int Delete (CNode *p);
CNode *Next () {if (current-＞next) {current=current-＞next;return current;} else return NULL;}
bool IsEmpty () {return n=0;}}
4 经优化后的算法
通常在实际应用中，邻接矩阵大多为稀疏矩阵，导致在计算过程中有大量∞参与运算。这就降低了算法的效率，所以改进算法将从消除冗余计算和冗余存储入手。
下面用链表数组MGraph G[n]来表示邻接矩阵，算法步骤如下：
1) 用与v0直接相连的顶点的权值对D[vi]进行初始化，其他设置为机器所允许的最大值。
2) 把与v0直接相连的顶点添加到链表Path中。
3) 在Path中找到权值最小的顶点w，并从中删除该顶点，如无剩余顶点则结束。
4) 在G里与w直接相连的其余各个顶点vi的权值中比较D[vi] s(w，vi)的大小，如果D[vi]小于D[vi] s(w，vi)，且如果D[vi]为∞则将vi添加到Path中，然后将P[vi]的前驱设置为w，并修改最短路径D[vi]= D[w] s(w，vi) 。以此重复步骤(2)。
下面给出改进后算法的C 核心源代码：
bool OptForDijkstra (MGraph *G,int v,int *p,int *D,int n)
{int w,i,min;
Path ph;
MNode *pnode;
CNode *cn1,*cn2;
if (v0＜1||v0＞n) return false;
for (i=0;i＜n;i ) {D[i]=INFINITY;p[i]=-1;}
pnode=G[v0].first;
while (pnode!=NULL)
{D[pnode-＞row]=pnode-＞vol;
CNode *l=newNode( );
l-＞row=pnode-＞row;
p[pnode-＞row]=v0;
ph.AddRear(l);
Pnode=pnode-＞next;}
while (!ph.IsEmpty( ))
{min=INFINITY;
cn2=ph.First( ) ;
while (cn2)
{if (D[cn2- ＞row]＜min)
{cn1=cn2;
w=cn1-＞row;
min=D[w];}
cn2=ph.Next( );
ph.Delete(cn1);
Pnode=G[w].first;
while ( pnode)
{if (D[pnode-＞row]＞(min pnode-＞vol))
{if (D[pnode- ＞row] ==INFINITY)（下轉第1734页）
（上接第1703页）
{CNode *pNode=newChainNode ( ) ;
pNode- ＞row=pnode- ＞row;
ph.AddRear (pNode ) ;}
D [pnode- ＞row] =min pnode- ＞vol;
P [pnode- ＞row] =w;}
pnode=pnode- ＞next;}}
return true;}}
5 算法复杂度分析
1) 时间复杂度：
我们分析这个优化后算法的运行时间。显然，步骤1的时间复杂度为o(n)，步骤2的时间复杂度为o(n)。而对于步骤3，第一次循环的次数等于与V0 直接相连的顶点数n1，第二次循环的次数为n1-1再加上与第一次找到的顶点直接相连并且与V0 的距离为无穷大的顶点的个数。依次类推，直到ph中顶点个数为0为止。最坏情况下如果V0与其余各顶点都有直接相连，则每次循环的次数为(n-1)，(n-2)，…1，那么时间复杂度为(n- 1) (n-2) … 1,即为o(n^2 )。观察步骤4，对于任何最短路径算法都至少对每条边检查一次，因为任何一条边都有可能在最短路径中，因此步骤4 的时间复杂度为o(T)，当T=n^2 时，复杂度为o(n^2)，此时和迪杰斯特拉的算法相同。
所以，经过优化算法的最坏时间复杂度为max{o(n)，o( T )，o(n^2 )}，即为o(n^2 )。
2) 空间复杂度：
优化后的算法采用链表数组作为存储结构，有效地消除了大量的冗余存储，因此空间复杂度为o(T),这里T为有向图的边数。在最差情况下即T=n^2时,算法的空间复杂度为o(n^2)。
6 结束语
经实际测试分析，当T＜＜n 时，即在稀疏图的情况下，这个改进的算法非常有用，有效地消除了大量的冗余计算和冗余存储，使得该算法的时间复杂度和空间复杂度都有优于经典的迪杰斯特拉算法。本优化算法操作性强，具有一定的实用价值。
参考文献：
[1] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997.
[2] 李春葆.数据结构考研指导[M].北京:清华大学出版社,2003.
[3] Bondy J A,Murty U S R.图论及其应用[M].北京:科学出版社,1984.
[4] Cormen T H,Charles E L,Ronald L R, et al.算法导论[M].2版,影印版.北京:高等教育出版社,2002.