请输入要查询的站点：
&的综合信息
此网站的网站缩略图
百度给该站流量：
ALEXA全球排名：&&ALEXA数据预估流量：IP ≈
电信响应：&&联通响应：
24小时收录
&在各大搜索引擎查询结果
&该网站IP:-&地址：-&有约-个站点运行在此服务器上&
&所在服务器相关信息
源文件大小
服务器类型
压缩后大小
&title meta值相关
标题（Title）
一般不超过80个字符
关键词（KeyWords）
一般不超过100个字符(分隔符一般使用逗号)
描述（Description）
一般不超过200个字符
&关键词密度
2%≦密度≦8%
Google排名
alexa近期排名趋势
排名变化趋势
一周平均排名
排名变化趋势
一月平均排名
排名变化趋势
三月平均排名
排名变化趋势宽度优先搜索 BFS
宽度优先搜索 BFS
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。
已知图G=(V,E)和一个源顶点s，宽度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有顶点，并计算s到所有这些顶点的距离(最少边数)，该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶点v，宽度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。
之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和末找到顶点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。
为了保持搜索的轨迹，宽度优先搜索为每个顶点着色：白色、灰色或黑色。算法开始前所有顶点都是白色，随着搜索的进行，各顶点会逐渐变成灰色，然后成为黑色。在搜索中第一次碰到一顶点时，我们说该顶点被发现，此时该顶点变为非白色顶点。因此，灰色和黑色顶点都已被发现，但是，宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式执行。若(u,v)∈E且顶点u为黑色，那么顶点v要么是灰色，要么是黑色，就是说，所有和黑色顶点邻接的顶点都已被发现。灰色顶点可以与一些白色顶点相邻接，它们代表着已找到和未找到顶点之间的边界。
在宽度优先搜索过程中建立了一棵宽度优先树，起始时只包含根节点，即源顶点s.在扫描已发现顶点u的邻接表的过程中每发现一个白色顶点v，该顶点v及边(u,v)就被添加到树中。在宽度优先树中，我们称结点u是结点v的先辈或父母结点。因为一个结点至多只能被发现一次，因此它最多只能有--个父母结点。相对根结点来说祖先和后裔关系的定义和通常一样：如果u处于树中从根s到结点v的路径中，那么u称为v的祖先，v是u的后裔。
下面的宽度优先搜索过程BFS假定输入图G=(V,E)采用邻接表表示，对于图中的每个顶点还采用了几种附加的数据结构，对每个顶点u∈V，其色彩存储于变量color[u]中，结点u的父母存于变量π[u]中。如果u没有父母(例如u=s或u还没有被检索到)，则
π[u]=NIL，由算法算出的源点s和顶点u之间的距离存于变量d[u]中，算法中使用了一个先进先出队列Q来存放灰色节点集合。其中head[Q]表示队列Q的队头元素，Enqueue(Q,v)表示将元素v入队， Dequeue(Q)表示对头元素出队；Adj[u]表示图中和u相邻的节点集合。
procedure BFS(G,S);
for 每个节点u∈V[G]-{s} do
color[u]←W
π[u]←NIL;
color[s]←G
π[s]←NIL;
while Q≠φ do
u←head[Q];
for 每个节点v∈Adj[u] do
if color[v]=White then
color[v]←G
d[v]←d[v]+1;
Enqueue(Q,v);
Dequeue(Q);
color[u]←B
展示了用BFS在例图上的搜索过程。黑色边是由BFS产生的树枝。每个节点u内的值为d[u]，图中所示的队列Q是第9-18行while循环中每次迭代起始时的队列。队列中每个结点下面是该结点与源结点的距离。
图1 BFS在一个无向图上的执行过程
&& 按如下方式执行，第1-4行置每个结点为白色，置d[u]为无穷大，每个结点的父母置为NIL，第5行置源结点S为灰色，即意味着过程开始时源结点已被发现。第6行初始化d[s]为0，第7行置源结点的父母结点为NIL，第8行初始化队列0，使其仅含源结点s，以后Q队列中仅包含灰色结点的集合。
程序的主循环在9-18行中，只要队列Q中还有灰色结点，即那些已被发现但还没有完全搜索其邻接表的结点，循环将一直进行下去。第10行确定队列头的灰色结点为u。第11-16行的循环考察u的邻接表中的每一个顶点v。如果v是白色结点，那么该结点还没有被发现过，算法通过执行第13-16行发现该结点。首先它被置为灰色，距离d[v]置为d[u]+1，而后u被记为该节点的父母，最后它被放在队列Q的队尾。当结点u的邻接表中的所有结点都被检索后，第17-18行使u弹出队列并置成黑色。
在证明宽度优先搜索的各种性质之前，我们先做一些相对简单的工作――分析算法在图G=(V,E)之上的运行时间。在初始化后，再没有任何结点又被置为白色。因此第12行的测试保证每个结点至多只能迸人队列一次，因而至多只能弹出队列一次。入队和出队操作需要O(1)的时间，因此队列操作所占用的全部时间为O(V)，因为只有当每个顶点将被弹出队列时才会查找其邻接表，因此每个顶点的邻接表至多被扫描一次。因为所有邻接表的长度和为Q(E)，所以扫描所有邻接表所花费时间至多为O(E)。初始化操作的开销为O(V)，因此过程BFS的全部运行时间为O(V+E)，由此可见，宽度优先搜索的运行时间是图的邻接表大小的一个线性函数。
在本部分的开始，我们讲过，对于一个图G=(V,E)，宽度优先搜索算法可以得到从已知源结点s∈V到每个可达结点的距离，我们定义最短路径长度δ(s,v)为从顶点s到顶点v的路径中具有最少边数的路径所包含的边数，若从s到v没有通路则为∞。具有这一距离δ(s,v)的路径即为从s到v的最短路径（后文我们将把最短路径推广到赋权图，其中每边都有一个实型的权值，一条路径的权是组成该路径所有边的权值之和，目前讨论的图都不是赋权图）。在证明宽度优先搜索计算出的就是最短路径长度之前，我们先看一下最短路径长度的一个重要性质。
设G=(V,E)是一个有向图或无向图，s∈V为G的任意一个结点，则对任意边(u,v)∈E,
δ(s,v)≤δ(s,u)+1
&&& 如果从顶点s可达顶点u，则从s也可达v。在这种情况下从s到v的最短路径不可能比从s到u的最短路径加上边(u,v)更长，因此不等式成立；如果从s不可达顶点u，则δ(s,v)=∞，不等式仍然成立。
我们试图说明对每个顶点v∈V，BFS过程算出的d[v]=δ(s,v)，下面我们首先证明d[v]是δ(s,v)的上界。
设G=(V,E)是一个有向或无向图，并假设算法BFS从G中一已知源结点s∈V开始执行，在执行终止时，对每个顶点v∈V，变量d[v]的值满足：d[v]≥δ(s,v)。
我们对一个顶点进入队列Q的次数进行归纳，我们归纳前假设在所有顶点v∈V，d[v]≥δ(s,v)成立。
归纳的基础是第8行当结点s被放入队列Q后的情形，这时归纳假设成立，因为对于任意结点v∈V-{s},d[s]=0=δ(s,s)且d[v]=∞≥δ(s,v)。
然后进行归纳，考虑从顶点u开始的搜索中发现一白色顶点v，按归纳假设，d[u]≥δ(s,u)。从过程第14行的赋值语句以及引理1可知
d[v]=d[u]+1≥δ(s,u)+1≥δ(s,v)
然后，结点v被插入队列Q中。它不会再次被插入队列，因为它已被置为灰色，而第13-16行的then子句只对白色结点进行操作，这样d[v]的值就不会改变，所以归纳假设成立。
为了证明d[v]=δ(s,v)，首先我们必须更精确地展示在BFS执行过程中是如何对队列进行操作的，下面一个引理说明无论何时，队列中的结点至多有两个不同的d值。
假设在图G=(V,E)之上的执行过程中，队列Q包含如下结点&v1,v2,...,vr&，其中v1是队列Q的头，vr是队列的尾，则d[vi]≤d[v1]+1且d[vi]≤d[vi+1],
i=1,2,..,r-1。
证明过程是对队列操作的次数进行归纳。初始时，队列仅包含顶点s，引理自然正确。
下面进行归纳，我们必须证明在压入和弹出一个顶点后引理仍然成立。如果队列的头v1被弹出队列，新的队头为v2(如果此时队列为空，引理无疑成立)，所以有d[vr]≤d[v1]+1≤d[v2]+1，余下的不等式依然成立，因此v2为队头时引理成立。要插入一个结点入队列需仔细分析过程BFS，在BFS的第16行，当顶点v加入队列成为vr+1时，队列头v1实际上就是正在扫描其邻接表的顶点u，因此有d[vr+1]=d[v]=d[u]+1=d[v1]+1，这时同样有d[vr]≤d[v1]+1=d[u]+1=d[v]=d[vr+1]，余下的不等式d[vr]≤d[vr+1]仍然成立，因此当结点v插入队列时引理同样正确。
现在我们可以证明宽度优先搜索算法能够正确地计算出最短路径长度。
定理1 宽度优先搜索的正确性
设G=(V,E)是一个有向图或无向图，并假设从G上某顶点s∈V开始执行，则在执行过程中，BFS可以发现源结点s可达的每一个结点v∈V，在运行终止时，对任意v∈V,d[v]=δ(s,v)。此外，对任意从s可达的节点v≠s，从s到v的最短路径之一是从s到π[v]的最短路径再加上边(π[v],v)。
我们先证明结点v是从s不可达的情形。由引理2，d[v]≥δ(s,v)=∞，根据过程第14行，顶点v不可能有一个有限的d[v]值，由归纳可知，不可能有满足下列条件的第一个顶点存在：该顶点的d值被过程的第14行语句置为∞，因此仅对有有限d值的顶点，第14行语句才会被执行。所以若v是不可达的话，它将不会在搜索中被发现。
证明主要是对由s可达的顶点来说的。设Vk表示和s距离为k的顶点集合，即Vk={v∈V:δ(s,v)=k}。证明过程为对k进行归纳。作为归纳假设，我们假定对于每一个顶点v∈Vk，在BFS的执行中只有某一特定时刻满足：
结点v为灰色；
d[v]被置为k；
如果v≠s，则对于某个u∈Vk-1，π[v]被置为u；
v被插入队列Q中；
正如我们先前所述，至多只有一个特定时刻满足上述条件。
归纳的初始情形为k=0，此时V0={s}，因为显然源结点s是唯一和s距离为0的结点，在初始化过程中，s被置为灰色，d[s]被置为0，且s被放人队列Q中，所以归纳假设成立。
下面进行归纳，我们须注意除非到算法终止，队列Q不为空，而且一旦某结点u被插入队列，d[u]和π[u]都不再改变。根据引理3可知如果在算法过程中结点按次序v1,v2,...,vr被插入队列，那么相应的距离序列是单调递增的：d[vi]≤d[vi+1]，i=1,2,...,r-1。
现在我们考虑任意结点v∈Vk，k≥1。根据单调性和d[v]≥k(由引理2)和归纳假设，可知如果v能够被发现，则必在Vk-1中的所有结点进入队列之后。
由δ(s,v)=k，可知从s到v有一条具有k边的通路，因此必存在某结点u∈Vk-1，且(u,v)∈E。不失一般性，设u是满足条件的第一个灰色节点(根据归纳可知集合Vk-1中的所有结点都被置为灰色)，BFS把每一个灰色结点放入队列中，这样由第10行可知结点u最终必然会作为队头出现。当已成为队头时，它的邻接表将被扫描就会发现结点v（结点v不可能在此之前被发现，因为它不与Vj(j&k-1)中的任何结点相邻接，否则v不可能属于Vk，并且根据假定，u是和v相邻接的Vk-1中被发现的第一个结点)。第13行置v为灰色，第14行置d[v]=d[u]+l=k，第15行置π[v]为u，第16行把v插入队列中。由于v是Vk中的任意结点，因此证明归纳假设成立。
在结束定理的证明前，我们注意到如果v∈Vk，则据我们所知可得π[v]∈Vk-1，这样我们就得到了一条从s到v的最短路径：即为从s到π[v]的最短路径再通过边(π[v],v)。
宽度优先树
过程BFS在搜索图的同时建立了一棵宽度优先树，如所示，这棵树是由每个结点的π域所表示。我们正式定义先辈子图如下，对于图G=(V,E)，源顶点为s，其先辈子图Gπ=(Vπ,Eπ)满足：
Vπ={v∈V:π[v]≠NIL}∪{s}
Eπ={(π[v],v)∈E:v∈Vπ-{s}}
如果Vπ由从s可达的顶点构成，那么先辈子图Gπ是一棵宽度优先树，并且对于所有v∈Vπ，Gπ中唯一的由s到v的简单路径也同样是G中从s到v的一条最短路径。由于它互相连通，且|Eπ|=|Vπ|-1(由树的性质)，所以宽度优先树事实上就是一棵树，Eπ中的边称为树枝。
当BFS从图G的源结点s开始执行后，下面的引理说明先辈子图是一棵宽度优先树。
当应用于某一有向或无向图G=(V,E)时，该过程同时建立的π域满足条件：其先辈子图Gπ=(Vπ,Eπ)是一棵宽度优先树。
过程BFS的第15行语句对(u,v)∈E且δ(s,v)&∞(即v从s可达)置π[v]=u，因此Vπ是由V中从v可达的顶点所组成，由于Gπ形成一棵树，所以它包含从s到Vπ中每一结点的唯一路径，由定理1进行归纳，我们可知其每条路径都是一条最短路径。(证毕)
下面的过程将打印出从S到v的最短路径上的所有结点，假定已经运行完BFS并得出了最短路径树。
procedure Print_Path(G,s,v);
then write(s)
else if π[v]=nil
then writeln('no path from ',s,' to ',v, 'exists.')
Print_Path(G,s,π[v]);
因为每次递归调用的路径都比前一次调用少一个顶点，所以该过程的运行时间是关于打印路径上顶点数的一个线性函数。图论中的优先级搜索——DFS,BFS,Prim,Dijkstra
在图算法中经常要执行遍历每个顶点和每条边的操作，即图搜索。许多图算法都以图搜索为基础，如2-着色问题、连通性计算基于深度优先搜寻（depth-first&search,&DFS），而无权最短路径则基于广度优先搜索（breadth-first&search，&BFS）。基于搜索的算法还包括计算最小生成树的Prim算法以及计算最短路径的Dijkstra算法，这4个算法就是今天的主题。我写这篇文章无意证明算法的正确和有效性，而是希望能揭示图搜索算法背后统一的思想。
非常简单，在搜索的过程中一旦遇到一个未标记的顶点，就沿着这个顶点继续搜索，直至遍历完所有可达的顶点。DFS具有回溯的性质，由此形成的搜索树很瘦很高。执行DFS时，同时会维护一个时间戳（time-stamp），以此记录每个顶点被搜索到的顺序，DFS形成的搜索树包含不同类型的边（树边，回边，下边以及交叉边），边的性质能通过时间戳识别出来。
则相反，遇到一个未搜索的顶点时，先将与该顶点邻接的搜索完，然后进入下一轮搜索。与源点距离为k+1的顶点总是在所有与源点距离小于等于k的所有顶点都搜索完之后才被遍历。对于不区分边权值的图，BFS能计算出最短路径——DFS对此无能为力。
是计算最小生成树（minimum&spanning&tree，MST）的经典算法，在计算最小生成树的过程中，Prim算法维护图的一个割（cut），割区分了树顶点（被选入MST的顶点）和非树顶点，树顶点集合构成了该图的部分MST（part&MST）。每一次向树顶点集合加入新顶点时，都选取距离部分MST最近的非树顶点，显然，相同的操作重复V-1次后，所有顶点都已加入树顶点集，最小生成树计算完毕。
可以解决非负权值的单源最短路径问题（shortest-paths&problem），我们可以采用与Prim算法几乎一样的思想：计算最短路径的过程中维护一棵最短路径树（shortest-paths&tree，SPT），包含了最短路径上的顶点。最开始这棵树中只有源点，作为树根。每次向SPT增加新顶点时，都选取非树顶点中与源点距离最近的顶点。相同的操作重复V-1次后，最短路径树计算完毕。与BFS类似，Dijkstra算法形成的搜索树偏胖~
仔细观察可以发现，这4种图搜索算法都具有相同的模式：首先它们都遍历了所有顶点，并且在遍历的过程中维护了一个顶点集，搜索一个顶点时把相邻的顶点按照某种规则加入到这个集合中，搜索下一个顶点时再按照某种规则从这个顶点集中取出顶点；取出顶点的规则是第二个共同点——它们都是贪心算法，在选择下一个顶点的时刻都依据某种优先级，选择优先级最大的顶点。
换言之，DFS、BFS、Prim算法和Dijkstra算法其实都是优先级优先搜索（priority-first&search，PFS），它们依赖预定义的优先级执行搜索，而存放顶点的顶点集就是广义优先队列（priority&queue，PQ）。显然，搜索算法的效率严重依赖于优先队列的操作效率。
既然这4种图搜索算法都有共同的思想，理所当然的，它们具有共同的代码接口（蓝色的函数调用包含与优先队列相关的操作）：
void&GraphPFS(Graph&G,&int&src)&{
&&PQinit(G,&src);
&&while&(!PQempty())&{
int&v&=&PQdelmax();&//&取出优先级最大的顶点
Update(v);
for&(t&=&G-&adj[v];&t&!=&NULL;&t&=&t-&next)&{
&&if&(ShouldInsert(t))
&&&&PQinsert(t,&v);&//&顶点t-&v加入优先队列
&&else&if&(ShouldChange(t))
&&&&PQchange(t,&v);&//&改变顶点t-&v的优先级
优先级搜索的算法接口基于图的邻接表（a）实现，其中顶点用int型数据表示，权值以double型表示，与的声明如下，graph中的V和E分别表示图中顶点和边的数目：
typedef&struct&Node*&L
struct&Node&{&int&v;&double&&Link&&};
typedef&struct&graph*&G
struct&graph&{&int&V,&E;&Link*&&};
函数完整地包含了优先级搜索的模式，只需要按照算法的要求选择合适的数据结构作为PQ，就能利用GraphPFS完成DFS、BFS、Prim算法和Dijkstra算法。
大动干戈地用优先级队列实现，无异于大炮打蚊子。但这个例子非常经典，所以我忍不住开一炮~
中的优先级是什么呢？DFS总是选择刚搜到的顶点进行下一轮搜索，显然，最近加入队列的顶点具有最高的优先级。不多想就能想到可以用栈（stack）作为DFS的PQ：栈总能访问到最近加入的元素。
#define&PQinit(G,&src)&&{&int&v;&\
&&&&for&(v&=&0;&v&&&G-&V;&++v)&\
ts[v]&=&-1;&\
&&&&cnt&=&0;&\
&&&&StackInit(G-&V);&\
&&&&StackPush(src);&\
ts[src]&=&cnt++;&\
#define&PQempty()&&&StackEmpty()
#define&PQdelmax()&&StackPop()
#define&Update(v)&&&ts[v]&=&cnt++
#define&ShouldInsert(t)
ts[t-&v]&==&-1
#define&PQinsert(t,&v)&&StackPush(t-&v)
#define&ShouldChange(t)&0
#define&PQchange(t,&v)
为了记录顶点的时间戳（time-stamp），增加了一个辅助数组ts，ts[v]&=&-1表示顶点v没有被访问过。Update记录了将顶点从PQ中取出时要更新的变化，在DFS中只需要记录时间戳即可，但不是所有的更新都在此处执行，有些更新还需要父顶点信息，所以在PQinsert中执行，在下一个例子中我们马上会遇到这种情况。DFS不需要中途改变优先级，所以PQchange定义为空操作。
不过要注意的是，DFS的PFS实现与直接递归实现有一些区别，递归DFS会在发现一个新顶点的时候立即进一步搜索，PFS是在遍历完邻接顶点后才选择下一个顶点，所以ts数组记录的时间戳会不一样。比如以0为源点遍历下面这个图：
的时间戳（time-stamp，ts）
直接递归的时间戳
虽然PFS与递归搜索的路径有所不同，但它仍然是正宗的深度优先搜寻，栈的结构确保了它总是优先沿着更深的路径搜索。
在BFS中，我们希望离源点近的顶点先被搜索，然后再搜索那些离源点更远的顶点。这要求先加入PQ的顶点要先被搜索，只要利用队列（queue）先进先出（first&in,&first&out，FIFO）的性质实现PQ就能达到目的。
#define&PQinit(G,&src)&&{&int&v;&\
&&&&for&(v&=&0;&v&&&G-&V;&++v)&\
&&&&&&pl[v]&=&-1;&\
&&&&QueueInit(G-&V);&\
&&&&QueuePut(src);&\
&&&&pl[src]&=&&\
#define&PQempty()&&QueueEmpty()
#define&PQdelmax()&&QueueGet()
#define&Update(v)
#define&ShouldInsert(t)&pl[t-&v]&==&-1
#define&PQinsert(t,&v)&&do&{
QueuePut(t-&v);&pl[t-&v]&=&v;
}&while(0)
#define&ShouldChange(t)&0
#define&PQchange(t,&v)
的结果以父链接表示的形式保存在pl（parent&link）数组中，父链接的意思就是BFS树中顶点的父节点，如若从源点s出发到顶点w的最短路径上要经过边v-w，那么pl[w]&=&v。BFS树根的父链接等于自身。另外pl数组也表示一个顶点是否有被搜索到，辅助了顶点集的插入操作。由于父链接的信息在插入顶点时已更新，所以Update不需要做任何事。
父链接表示最终结果
还可以获取到许多信息，比如顶点到源点之间经过的边数，以及BFS的时间戳等等，只要向PQinsert和Update内加入相应的代码即可获取。
和BFS几乎是最简单的图算法，现在来个稍微高级一点的——最小生成树（minimum&spanning&tree，MST）。Prim算法的思想在文章最开始的时候就说过了，现在从PFS的角度审视这个算法。
算法计算MST的过程中维护了一个割（cut），区分了树（tree）顶点和非树（nontree）顶点，树顶点即是被选入MST的顶点。显然的，每一次从PQ中取出的顶点应该都是树顶点，关键在于：如何确定顶点的优先级（priority）？
由于Prim算法的框架是每次选择距离树最近的非树顶点，选择V-1次之后计算结束，因此顶点的优先级理所应当的由非树顶点与树顶点之间的距离决定，距树最近的非树顶点具有最大的优先级。
确定了优先级之后，接下来要做的就是挑选合适的数据结构充当PQ。事实上我们有许多选择：无序数组、有序数组、自组织链表，都可以。但注意到队列操作的效率直接决定了整个算法的效率，我们应当选择能够快速插入和搜索最大值的数据结构，显然堆（heap）可以胜任。注意各顶点的优先级不是一开始就明确的，而是可能在搜索过程中发生变化，所以堆还必须具有修改元素优先级的功能。普通的堆没有这样的功能，而索引堆（即以目标数组的索引作为元素的堆）可以轻松实现这个功能，所以我们选择索引堆作为PQ（P.S.&不熟悉索引堆的读者请google“索引堆”，点击第一个搜索结果&:-)）。
好了，PQ的数据结构也选好了，接下来考虑如何表示Prim算法的中间过程和结果。
首先，Prim算法计算的是MST，表示一棵树的方式在BFS中已经介绍过一种，既父链接表示。这种表示非常方便更新，所以在Prim算法中同样使用一个pl（parent&link）数组存放最终形成的MST父链接结构。
其次，刚才提到索引堆的元素是目标数组的索引，目标数组涉及到顶点的优先级，因此目标数组的元素即是各个非树顶点到MST的距离。由于边权值是double型，所以用一个double的dist（distance）数组作为索引堆的目标数组。
最后，在计算MST的每一步中，都要知道当前与每个非树顶点最近的树顶点，才能从其中选出所有非树顶点中与MST最近的的一个。这些信息保存在fr（fringe）数组中。换言之，fr存放了阶段性的搜索结果。
以上这些信息的保存方式与PQ一样有许多选择，但最简单的实现是使用顶点索引数组。OK，现在可以上代码了。
#define&P&&&&&&&&&&&&&&t-&wt
#define&PQinit(G,&src)&&{&int&v;&\
&&&&for&(v&=&0;&v&&&G-&V;&++v)&{&\
&&&&&&pl[v]&=&-1;&fr[v]&=&-1;&\
&&&&PQInit(G-&V);&\
&&&&priority&=&&\
&&&&fr[src]&=&&\
&&&&PQInsert(src);&\
#define&PQempty()&&PQEmpty()
#define&PQdelmax()&&PQDelmin()
#define&Update(v)&&pl[v]&=&fr[v]
#define&ShouldInsert(t)&fr[t-&v]&==&-1
#define&PQinsert(t,&v)&&do&{&\
&&&&dist[t-&v]&=&P;&PQInsert(t-&v);&fr[t-&v]&=&v;&\
}&while(0)
#define&ShouldChange(t)&(pl[t-&v]&==&-1)&&&&(P&&&dist[t-&v])
#define&PQchange(t,&v)&&do&{&\
&&&&dist[t-&v]&=&P;&PQDec(t-&v);&fr[t-&v]&=&v;&\
}&while(0)
第一行用P表示优先级，即树顶点到非树顶点直接的距离t-&wt，可以简化代码。PQinit重置了pl和fr，并设置了PQ的目标数组（priority&=&dist）。随后初始化索引堆并将源点插入索引堆。由于PQDelmin选出的顶点必然属于MST，所以Update可以放心地设置它的父链接。
算法的重点在于PQinsert和PQchange。在搜索顶点的过程中，如果一个顶点w是通过v首次被搜索到（w&=&t-&v，fr[t-&v]&==&-1），显然目前没有其它路径比v-w更短了，随即可以设置dist[w]和fr[w]，并将w插入PQ。另一方面，如果通过v遇到了一个已知的非树顶点w，并且v-w的距离比已知距离更短，此时就该通过PQchange修改顶点w的优先级——变高了。
经过V-1次迭代，所有的顶点最终都会成为树顶点。
伟大的Dijkstra又登场了。
算法用于计算无负权值图的单源最短路径，与Prim算法一样，我们从PFS出发，一一解决Dijkstra算法中将要遇到的问题。
既然是求最短路径，优先级当然由顶点到源点的路径长度决定，路径长度越短，优先级越高。与Prim算法一样，PQ仍然可以用索引堆实现。
与Prim算法一样的还有最终结果的表示。Dijkstra算法计算最短路径，最终结果应该完整地包含这两个信息：一、最短路径怎么走；二、最短路径的长度。第一个信息，首先最短路径肯定不会包含环，所以可以用最短路径树（shortest-paths&tree，SPT）的方式表示，表示树的简便方法我们已经很熟悉了，用一个父链接数组pl即可。第二个信息更不用想：一个dist数组，dist[v]即表示顶点v到源点s的距离。
算法的运行方式如同文章开头所写，维护一棵SPT，最开始只有源点。随后逐步向SPT中添加非树顶点，规则是每一次都选择距离源点最近的非树顶点。遍历顶点的同时，反复地执行一项被称为松弛（relaxation）的操作——对于顶点v，每当遇到一个比已知从源点到达v的最短路径还要短的路径，就更新关于v的路径信息（其实我觉得“松弛”这个术语很不恰当，一旦遇到更短的路径，那么这条路径应该更短更紧才对，怎么会是“松弛”呢？）。松弛是在遍历顶点的过程中进行的，从PQ中取出V-1个顶点、或所有可达顶点后，算法结束。
#define&P&&&&&
dist[v]&+&t-&wt
#define&PQinit(G,&src)&
&&&&PQInit(G-&V);&\
&&&&priority&=&&\
&&&&int&v;&\
&&&&for&(v&=&0;&v&&&G-&V;&++v)&{&\
&&&&&&pl[v]&=&-1;&dist[v]&=&MAX_WT;&PQInsert(v);&\
&&&&dist[src]&=&0.0;&\
&&&&PQDec(src);&\
#define&PQempty()
#define&PQdelmax()
PQDelmin()
#define&Update(v)
if&(wt[v]&==&MAX_WT)&
#define&ShouldInsert(t)&
#define&PQinsert(t,&v)
#define&ShouldChange(t)&
P&&&wt[t-&v]
#define&PQchange(t,&v)&&
&&&&wt[t-&v]&=&P;&PQDec(t-&v);&pl[t-&v]&=&v;&\
}&while&(0)
算法同样定义了一个P，即源点到目标顶点的距离，方便写代码。注意算法初始化PQ的时候就已经把所有顶点都插入索引堆（为什么？），因此PQinsert也不需要做任何事情，这也是Dijkstra算法与Prim算法的一个区别。刚才提到Dijkstra算法在计算完所有从源点可达的顶点后结束，此处不可达的顶点以距离MAX_WT表示，所以Update做的事情并不是更新什么信息，而是判断当前是否遇到了一个不可到达的顶点，如果是，那么算法也没有继续进行下去的必要了。初始情况下，顶点到自己的距离为0，其它所有顶点都不可达，随着松弛操作的进行，其它顶点的正确路径信息也会慢慢明晰，所有的松弛操作都在PQchange内完成。
算法与Prim算法是如此的相似，所以把它们对比一下是件有趣的事情。它们的相通之处贯穿全文：优先级优先搜索的本质。然而它们有个明显的区别，即刚才提到的：Prim算法在计算过程中多维护了一个fr数组，记录每一步当前与每个非树顶点最近的树顶点，每当遇到一个未曾搜索过的顶点就加入到fr。
之所以要这样做是因为Prim算法必须区分树顶点和非树顶点，Prim的优先级取决于非树顶点与树的距离，必须在计算过程中保存这些中间结果——每个非树顶点所关联的最近的树顶点。Dijkstra算法不需要，所以一开始就把所有顶点插入到PQ中，然后不断地松弛。其实Dijkstra算法也要做出某种区分，然而它只需要区分源点和非源点……
无论是“看起来不太像”的DFS和BFS，还是“看起来很像”的Prim算法和Dijkstra算法，都通过优先级优先搜索（PFS）这一算法思想联系到一起。现在再度总结一下：PFS是一种搜索图（Graph）的一般性算法，它先将图中的顶点（部分或全部地）加入到一个广义的优先队列中，然后根据特定的优先级，每次从队列里选取一条优先级最高的边，加入到特定的搜索树。搜索树就是PFS的最终结果（如最小生成树、最短路径树、DFS树……）。由此，DFS、BFS、Prim算法和Dijkstra算法都表征出相同的思想：
优先队列（PQ）
边权值/t-&wt
路径长度/dist[v]&+&t-&wt
其实，你可以选择任何你想得到的优先级对图进行搜索，也许会得到意想不到的结果哦~
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。}