2014年9月22日纸上谈兵:最短路径与贪婪-Vamei-博客园
http://www.cnblogs.com/vamei/p/3604629.html1/14
纸上谈兵:最短路径与贪婪
作者：Vamei出处：http://www.cnblogs.com/vamei欢迎转载，也请保留这
段声明。谢谢!
图是由节点和连接节点的边构成的。节点之间可以由路径，即边的序列。根据路径，可
以从一点到达另一点。在一个复杂的图中，图中两点可以存在许多路径。最短路径讨论
了一个非常简单的图论问题，图中从A点到B点，那条路径耗费最短？
这个问题又异常复杂，因为网络的构成状况可能很复杂。
一个最简单的思路，是找出所有可能的从A到B的路径，再通过比较，来寻找最短路径。
然而，这并没有将问题简化多少。因为搜索从A到B的路径，这本身就是很复杂的事情。
而我们在搜索所有路径的过程中，有许多路径已经绕了很远，完全没有搜索的必要。比
如从上海到纽约的路线，完全没有必要先从上海飞到南极，再从南极飞到纽约，尽管这
2014年9月22日纸上谈兵:最短路径与贪婪-Vamei-博客园
http://www.cnblogs.com/vamei/p/3604629.html2/14
一路径也是一条可行的路径。
所以，我们需要这样一个算法：它可以搜索路径，并当已知路径包括最短路径时，即停
止搜索。我们先以无权网络为例，看一个可行的最短路径算法。
无权网络(unweightednetwork)是相对于加权网络的，这里的“权”是权重。每条
边的耗费相同，都为1。路径的总耗费即为路径上边的总数。
我们用“甩鞭子”的方式，来寻找最短路径。鞭子的长度代表路径的距离。
无权网络
2014年9月22日纸上谈兵:最短路径与贪婪-Vamei-博客园
http://www.cnblogs.com/vamei/p/3604629.html3/14
手拿一个特定长度的鞭子，站在A点。甩出鞭子，能打到一些点。比如C和D。
将鞭子的长度增加1。再甩出鞭子。此时，从C或D出发，寻找距离为1的邻接点，即E和
F。这些点到A点的距离，为此时鞭子的长度。
记录点E和F，并记录它们的上游节点。比如E(C)，F(D)。我们同样可以记录此时该
点到A的距离，比如5。
如果要记录节点E时，发现它已经出现在之前的记录中，这说明曾经有更短的距离到E。
此时，不将E放入记录中。毕竟，我们感兴趣的是最短路径。如下图中的E：
2014年9月22日纸上谈兵:最短路径与贪婪-Vamei-博客园
http://www.cnblogs.com/vamei/p/3604629.html4/14
黄色的E不被记录
最初的鞭子长度为0，站在A点，只能打到A点自身。当我们不断增加鞭子长度，第一次
可以打到B时，那么此时鞭子的长度，就是从A到B的最短距离。循着我们的记录，倒推
上游的节点，就可以找出整个最短路径。
我们的记录本是个很有意思的东西。某个点放入记录时，此时的距离，都是A点到该点
的最短路径。根据记录，我们可以反推出记录中任何一点的最短路径。这就好像真诚对
待每个人。这能保证，当你遇到真爱时，你已经是在真诚相待了。实际上，记录将所有
节点分割成两个世界：记录内的，已知最短距离的；记录外的，未知的。
在加权网络中(weightednetwork)，每条边有各自的权重。当我们选择某个路径
时，总耗费为路径上所有边的权重之和。
加权网络在生活中很常见，比如从北京到上海，可以坐火车，也可以坐飞机。但两种选
择耗费的时间并不同。再比如，我们打出租车和坐公交车，都可以到市区，但车资也有
所不同。在计算机网络中，由于硬件性能不同，连接的传输速度也有所差异。加权网络
正适用于以上场景。无权网络是加权网络的一个特例。
加权网络
2014年9月22日纸上谈兵:最短路径与贪婪-Vamei-博客园
http://www.cnblogs.com/vamei/p/3604629.html5/14
这个问题看起来和无权网络颇为类似。但如果套用上面的方法，我们会发现，记录中的
节点并不一定是最短距离。我们看下面的例子：
很明显，最短路径是A->C->D->B，因为它的总耗费只有4。按照上面的方法，我们先
将A放入记录。从A出发，有B和C两个如果将B和C同时放入记录，那么记录中的B并不符
合最短距离的要求。
那么，为什么无权网络可行呢？假设某次记录时，鞭子长度为5，那么这次记录点的邻
接点，必然是距离为6的点。如果这些邻接点没有出现过，那么6就是它们的最短距离。
所有第一次出现的邻接点，都将加入到下次的记录中。比如下面的例子，C/D/E是到达
A的邻接点，它们到A的最短距离必然都是1。
对于加权网络来说，即使知道了邻接点，也无法判断它们是否符合最短距离。在记录
C/D/E时，我们无法判断未来是否存在如下图虚线的连接，导致A的邻接点E并不是下一
步的最短距离点：
2014年9月22日纸上谈兵:最短路径与贪婪-Vamei-博客园
http://www.cnblogs.com/vamei/p/3604629.html6/14
但情况并没有我们想的那么糟糕。仔细观察，我们发现，虽然无法一次判定所有的邻接
点为下一步的最短距离点，但我们可以确定点C已经处在从A出发的最短距离状态。A到C
的其它可能性，比如途径D和E，必然导致更大的成本。
也就是说，邻接点中，有一个达到了最短距离点，即邻接点中，到达A距离最短的点，
比如上面的C。我们可以安全的把C改为已知点。A和C都是已知点，点P成为新的邻接
点。P到A得距离为4。
出于上面的观察，我们可以将节点分为三种：
已知点：已知到达A最短距离的点。“我是成功人士。”
邻接点：有从记录点出发的边，直接相邻的点。“和成功人士接触，也有成功的机
会哦。”
未知点：“还早得很。”
最初的已知点只有A。已知点的直接下游节点为邻接点。对于邻接点，我们需要独立的
记录它们。我们要记录的有：
当前情况下，从A点出发到达该邻接点的最短距离。比如对于上面的点D，为6。
此最短距离下的上游节点。对于上面的点D来说，为A。
2014年9月22日纸上谈兵:最短路径与贪婪-Vamei-博客园
http://www.cnblogs.com/vamei/p/3604629.html7/14
每次，我们将邻接点中最短距离最小的点X转为已知点，并将该点的直接下游节点，改
为邻接点。我们需要计算从A出发，经由X，到达这些新增邻接点的距离：新距离=X
最短距离+QX边的权重。此时有两种情况，
如果下游节点Q还不是邻接点，那么直接加入，Q最短距离=新距离，Q上游节点
为X。
如果下游节点Q已经是邻接点，记录在册的上游节点为Y，最短距离为y。如果新
距离小于y，那么最小距离改为新距离，上游节点也改为X。否则保持原记录不
变。
我们还用上面的图，探索A到E的路径：
第一步
状态已知距离上游
A已知0A
C邻接1A
D邻接6A
E邻接9A
P未知无穷
第二步
状态已知距离上游
A已知0A
C已知1A
D邻接6A
E邻接9A
P邻接4C
第二步
已知距上
2014年9月22日纸上谈兵:最短路径与贪婪-Vamei-博客园
http://www.cnblogs.com/vamei/p/3604629.html8/14
状态离游
A已知0A
C已知1A
D邻接6A
E邻接7P
P已知4C
第三步
状态已知距离上游
A已知0A
C已知1A
D已知6A
E邻接7P
P已知4C
最后，E成为已知。倒退，可以知道路径为E,P,C,A。正过来，就是从A到E的最短
路径了。
上面的算法是经典的Dijkstra算法。本质上，每个邻接点记录的，是基于已知点的情
况下，最好的选择，也就是所谓的“贪婪算法”(greedyalgorithm)。当我们贪婪
时，我们的决定是临时的，并没有做出最终的决定。转换某个点成为已知点后，我们增
加了新的可能性，贪婪再次起作用。根据对比。随后，某个邻接点成为新的“贪无可
贪”的点，即经由其它任意邻接点，到达该点都只会造成更高的成本；经由未知点到达
该点更不可能，因为未知点还没有开放，必然需要经过现有的邻接点到达，只会更加绕
远。好吧，该点再也没有贪婪的动力，就被扔到“成功人士”里，成为已知点。成功学不
断传染，最后感染到目标节点B，我们就找到了B的最短路径。
理解了上面的原理，算法的实现是小菜一碟。我们借用图(graph)中的数据结构，略
微修改，构建加权图。
实现
2014年9月22日纸上谈兵:最短路径与贪婪-Vamei-博客园
http://www.cnblogs.com/vamei/p/3604629.html9/14
我们将上面的表格做成数组records，用于记录路径探索的信息。
重新给点A,C,D,E,P命名，为0,1,2,3,4。
代码如下：
/ByVamei/
#include
#include
#defineNUM_V5
#defineINFINITY10000
typedefstructnodeposition;
typedefstructrecordlabel;
/node/
structnode{
intelement;
positionnext;
intweight;
};
/tableelement,keeprecord/
structrecord{
intstatus;
intdistance;
intprevious;
};
/
operations(stereotype)
/
voidinsert_edge(position,int,int,int);
voidprint_graph(position,int);
intnew_neighbors(position,label,int,int);
voidshortest_path(position,label,int,int,int);
2014年9月22日纸上谈兵:最短路径与贪婪-Vamei-博客园
http://www.cnblogs.com/vamei/p/3604629.html10/14
/fortestingpurpose/
voidmain()
{
structnodegraph[NUM_V];
structrecordrecords[NUM_V];
inti;
//initializethevertices
for(i=0;i
(graph+i)->element=i;
(graph+i)->next=NULL;
(graph+i)->weight=-1;
}
//insertedges
insert_edge(graph,0,1,1);
insert_edge(graph,0,2,6);
insert_edge(graph,0,3,9);
insert_edge(graph,1,4,3);
insert_edge(graph,4,3,3);
print_graph(graph,NUM_V);
//initializethebook
for(i=0;i
(records+i)->status=-1;
(records+i)->distance=INFINITY;
(records+i)->previous=-1;
}
shortest_path(graph,records,NUM_V,0,3);
//
}
voidshortest_path(positiongraph,labelrecords,intnv,
intstart,intend){
intcurrent;
(records+start)->status=1;
(records+start)->distance=0;
2014年9月22日纸上谈兵:最短路径与贪婪-Vamei-博客园
http://www.cnblogs.com/vamei/p/3604629.html11/14
(records+start)->previous=0;
current=start;
while(current!=end){
current=new_neighbors(graph,records,nv,
current);
}
while(current!=start){
printf("%d<-",current);
current=(records+current)->previous;
}
printf("%d\n",current);
}
intnew_neighbors(positiongraph,labelrecords,intnv,int
current){
intnewDist;
intv;
inti;
intd;
positionp;
//updatethecurrentknown
(records+current)->status=1;
//UPDATEnewneighbors
p=(graph+current)->next;
while(p!=NULL){
v=p->element;
(records+v)->status=0;
newDist=p->weight+(records+current)->distance;
if((records+v)->distance>newDist){
(records+v)->distance=newDist;
(records+v)->previous=current;
}
p=p->next;
}
2014年9月22日纸上谈兵:最短路径与贪婪-Vamei-博客园
http://www.cnblogs.com/vamei/p/3604629.html12/14
//findthenextknown
d=INFINITY;
for(i=0;i
if((records+i)->status==0&&(records+i)-
>distance
d=(records+i)->distance;
v=i;
}
}
returnv;
}
/printthegraph/
voidprint_graph(positiongraph,intnv){
inti;
positionp;
for(i=0;i
p=(graph+i)->next;
printf("From%3d:",i);
while(p!=NULL){
printf("%d->%d;w:%d",i,p->element,p-
>weight);
p=p->next;
}
printf("\n");
}
}
/
insertanedge
withweight
/
voidinsert_edge(positiongraph,intfrom,intto,int
weight)
{
positionnp;
positionnodeAddr;
np=graph+from;
2014年9月22日纸上谈兵:最短路径与贪婪-Vamei-博客园
http://www.cnblogs.com/vamei/p/3604629.html13/14
nodeAddr=(position)malloc(sizeof(structnode));
nodeAddr->element=to;
nodeAddr->next=np->next;
nodeAddr->weight=weight;
np->next=nodeAddr;
}
运行结果如下：
From0:0->3;w:90->2;w:60->1;w:1
From1:1->4;w:3
From2:
From3:
From4:4->3;w:3
3<-4<-1<-0
即从0到1到4到3，也就是从A到C到P到E，是我们的最短路径。
上面的算法中，最坏情况是目标节点最后成为已知点，即要寻找[]。而每个已知
点是通过寻找[]个节点的最小值得到的。最后，打印出最短的路径过程中，需要
倒退，最多可能有[]，也就是说，算法复杂度为[]。
上面的records为一个数组，用于记录路径探索信息。我们可以用一个优先队列来代替
它，将已知的节点移除优先队列。这样可以达到更好的运算效率。
练习:自行设计一个加权网络，寻找最短路径。
最短路径是寻找最优解的算法。在复杂的网络中，简单的实现方式无法运行，必须求助
O(|V|)
O(|V|)
O|E|O(|V+|E|)|2
总结
2014年9月22日纸上谈兵:最短路径与贪婪-Vamei-博客园
http://www.cnblogs.com/vamei/p/3604629.html14/14
于精心设计的算法，比如这里的Dijkstra算法。利用贪婪的思想，我们不断的优化结
果，直到找到最优解。
欢迎阅读“纸上谈兵:算法与数据结构”系列
分类:算法
标签:算法
|
|
