在之前的中，博主给出了最短路径的一些基本概念和问题，并且给出了对权值不能为负的图使用Dijkstra算法求解单源最短路径问题的方法。
　　我们提到，Dijkstra算法的一个巨大前提是：不能有权值为负的边。因为当权值可以为负时，可能在图中会存在负权回路，最短路径只要无限次地走这个负权回路，便可以无限制地减少它的最短路径权值，这就变相地说明最短路径不存在，Dijkstra算法无法终止。下图说明从u到v的最短路径是不存在的。
　　那么，应该用什么方法求解？
　　上面我们说Dijkstra算法无法终止，我们可能会想，可不可以试图让Dijkstra算法终止呢？
　　当Dijkstra算法运行时，突然找到了一个负权回路，这下糟糕做不下去了，那么赶快终止算法跳出循环，报告给我们：我找到了负权回路。
　　这个想法是很好的，但是如何判断碰到负权回路是个问题，读者有兴趣可以去实践一下。
　　为了处理存在负权边的情况，我们采用另外一种非常著名的方法：Bellman_Ford算法。有关最短路径的相关问题以及Dijkstra算法的求解，可参看下列博客：
二、Bellman_Ford算法思想
　　如果图G中存在负权回路，那么某些最短路径是不存在的。
　　Bellman_Ford算法的基本思想是：计算从源顶点s到其他所有顶点的最短路径权值，若碰上负权回路，则报告存在负权回路并返回。
　　若图中无负权回路，Bellman_Ford算法最多需要经过|V|-1次对所有边的松弛操作，就可以得到结果（有关证明请google）。当结束|V|-1次操作之后，在外围再做一次对所有边的松弛操作的测试，若到某些顶点的最短路径权值还能减小，说明|V|-1次松弛没有得到最后结果，那么必定存在负权回路，直接返回；若不再减小，说明已找到最短路。有关详情可看伪代码注释。
　　伪代码如下：
Bellman_Ford(G, w, s)
　　　　d[s]&0　　//初始化，s到s最短路权值为0，其他为正无穷
　　　　for each v&V-{s}
　　　　　　d[v]&&
　　　　　　　　　　　　parent[v]& NIL　　//为生成最短路径树起作用
　　　　for i & 1 to |V|-1　　// 实验证明最多只需|V|-1次外层循环，|V|-1次结束后，若图G中无负权回路，那么s到其他所有顶点的最短路径求得
　　　　　　do for each edge (u, v)&E
　　//算法核心，松弛每一条边，维持三角不等式成立
　　　　　　　　do if d[v] & d[u] + w(u, v)
　　　　　　　　　　then d[v] & d[u]+w(u, v)
　　　　　　　　　　　　　　　　　　　　　　　　
parent[v]&u
　　　　for each edge (u, v)&E　　　　//进行完|V|-1次循环操作后，如果还能某条边还能进行松弛，说明到某个点的最短路径还未找到，那么必定是存在负权回路，返回FALSE
　　　　　　do if d[v] & d[u] + w(u, v)
　　　　　　　　then return FALSE
　　　　return TRUE　　　　//若进行上面的松弛之后没有返回，说明所有的d值都不会再改变了，那么最短路径权值完全找到，返回TRUE
三、简单例子说明
　　下面给出一个简单的例子来模拟Bellman_Ford算法的过程，因为在|V|-1次循环中，我们需要做的是试图松弛每一条边，为了方便起见，我们给每一条边进行编号，然后按编号进行松弛，这样的话计算机实现比较方便，而且对结果不会产生影响。
　　初始情况：
　　第一轮，按顺序可松弛边4和边5，更新顶点B和C：
　　第二轮，按顺序可松弛边1、3、7、8，更新顶点E、D、C、D：
　　第三轮，进行一轮后发现无变化，跳出循环。
　　注：若存在负权回路，那么|V|-1必定全部做完，因为每次都可以更新，减去这个负权回路的值。
四、代码实现
　　下面给出Bellman_Ford算法的C/C++实现，其中可进行部分的优化。
　　我们发现，在进行|V|-1次循环操作时，每次的更新都与顶点的d的值有关，若所有d值不再改变了，那就不会影响到下一次的结果，那么我们就可以提前跳出循环，避免下面不必要的操作。
　　实现：
1 #include &iostream&
2 #include &cstdio&
3 using namespace
5 #define INF 0xffff
//权值上限
6 #define maxe 5000
//边数上限
7 #define maxn 100
//顶点数上限
//顶点数、边数
9 int d[maxn];
//保存最短路径权值的数组
10 int parent[maxn];
//每个顶点的前驱顶点，用以还原最短路径树
11 struct edge
//表述边的结构体，因为要对每一条边松弛
//u为边起点，v为边端点，w为边权值，可以为负
14 }EG[maxe];
16 bool Bellman_Ford(int s)
//计算从起点到所有顶点的
for(int i = 1; i &= i++)
//初始化操作d[EG[j].v] & d[EG[j].u]+EG[j].w
d[i] = INF;
parent[i] = -1;
//标记，判断d值是否更新，跳出外层循环的依据
for(int i = 1; i & i++)
//外层循环最多做n-1次
flag = false;
//初始为false,假设不需再更新
for(int j = 0; j & j++)
//对m条边进行松弛操作，若有更新，flag记为true
if(d[EG[j].v] & d[EG[j].u]+EG[j].w)
//if d[v] & d[u] + w(u, v)，更新d[v]
d[EG[j].v] = d[EG[j].u]+EG[j].w;
parent[EG[j].v] = EG[j].u;
flag = true;
if(!flag) break; //若松弛完每条边后，flag状态不变，说明未发现更新，可直接跳出循环
for(int i = 0; i & i++)
//做完上述松弛后，如果还能松弛，说明存在负权回路，返回false
if(d[EG[i].v] & d[EG[i].u]+EG[i].w)
return false;
return true;
//不存在负权回路，返回true
43 int main()
printf("请输入n和m:\n");
scanf("%d%d", &n, &m);
printf("请输入m条边(u, v, w)：\n");
for(int i = 0; i & i++)
scanf("%d%d%d", &EG[i].u, &EG[i].v, &EG[i].w);
printf("请输入起点：");
scanf("%d", &st);
if(Bellman_Ford(st))
printf("不存在负权回路。\n");
printf("源顶点到各顶点的最短路径权值为：\n");
for(int i = 1; i &= i++)
printf("%d ", d[i]);
printf("\n");
五、测试结果
就上面例子，我们进行测试，其中点都换成了数字形式：
六、时间复杂度分析
　　Bellman_Ford算法实现起来相比使用优先队列的Dijkstra算法要简单许多，但是时间复杂度不如Dijkstra算法，从代码分析，我们可以看出它的复杂度为O(VE)，V表示顶点个数，E表示边的条数。但是，至少现在我们可以对负权值情况进行求解。
（转载请注明出处。）
阅读(...) 评论()3255人阅读
数据结构（6）
算法分析（3）
Dijkstra算法当中将节点分为已求得最短路径的集合（记为S）和未确定最短路径的个集合（记为U），归入S集合的节点的最短路径及其长度不再变更，如果边上的权值允许为负值，那么有可能出现当与S内某点（记为a）以负边相连的点（记为b）确定其最短路径时，它的最短路径长度加上这条负边的权值结果小于a原先确定的最短路径长度，而此时a在Dijkstra算法下是无法更新的，由此便可能得不到正确的结果。求带负权值边的单源最短路径可以用贝尔曼-福特算法。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：44716次
排名：千里之外
原创：15篇
转载：35篇
(1)(1)(1)(1)(2)(1)(1)(1)(3)(2)(5)(2)(1)(2)(1)(2)(1)(1)(2)(16)(2)(1)您所在的位置： &
详谈Dijkstra算法
详谈Dijkstra算法
Dijkstra算法是典型的最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
本文由单源最短路径路径问题开始，而后描述Bellman-Ford算法，到具体阐述Dijkstra算法，阐述详细剖析Dijkstra算法的每一个步骤，教你彻底理解此Dijkstra算法。
一、单源最短路径问题
我们知道，单源最短路径问题：已知图G=(V，E)，要求找出从某个定源顶点s&-V，到每个v&-V的最短路径。简单来说，就是一个图G中，找到一个定点s，然后以s为起点，要求找出s到图G中其余各个点的最短距离或路径。
此单源最短路径问题有以下几个变形：
I、& 单终点最短路径问题：&每个顶点v到指定终点t的最短路径问题。即单源最短路径问题的相对问题。
II、 单对顶点最短路径问题：给定顶点u和v，找出从u到v的一条最短路径。
III、每对顶点间最短路径问题：
针对任意每俩个顶点u和v，找出从u到v的最短路径。最简单的想法是，将每个顶点作为源点，运行一次单源算法即可以解决这个问题。当然，还有更好的办法。&
二、Bellman-Ford 算法
1、回路问题
一条最短路径不能包含负权回路，也不能包含正权回路。一些最短路径的算法，如Dijkstra 算法，要求图中所有的边的权值都是非负的，如在公路地图上，找一条从定点s到目的顶点v的最短路径问题。
2、Bellman-Ford 算法
而Bellman-Ford 算法，则允许输入图中存在负权边，只要不存在从源点可达的负权回路，即可。简单的说，图中可以存在负权边，但此条负权边，构不成负权回路，不影响回路的形成。且，Bellman-Ford 算法本身，便是可判断图中是否存在从源点可达的负权回路，若存在负权回路，算法返回FALSE,若不存在，返回TRUE。
Bellman-Ford 算法的具体描述
BELLMAN-FORD(G, w, s)
INITIALIZE-SINGLE-SOURCE(G,&s)&&&&for&i&&&1&to&|V[G]|&-&1 &&&do&for&each&edge&(u,&v)&&&E[G] &do&RELAX(u,&v,&w)&&&&&for&each&edge&(u,&v)&&&E[G] &do&if&d[v]&&&d[u]&+&w(u,&v) &then&return&FALSE&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&return&TRUE&&&&&&&&&&&&&&&&&&&&&&&
Bellman-Ford 算法的时间复杂度，由上可得为O（V*E）。
3、关于判断图中是否包含负权回路的问题：
根据定理，我们假定，u是v的父辈，或父母，那么，当G(V,E)是一个有向图或无向图(且不包含任何负权回路)，s&-V，s为G的任意一个顶点，则对任意边(u，v)&-V，有&&&&&
d[s，v] &= d[s，u]+1
此定理的详细证明，可参考算法导论一书上，第22章中引理22.1的证明。或者根据第24章中通过三角不等式论证Bellman-Ford算法的正确性，也可得出上述定理的变形。
即假设图G中不包含负权回路，可证得
d[v]=$(s，u) &&&&&&&&=$(s，u)+w(u，v)&&&&&&&&&=d[u]+w[u，v]&
所以，在不包含负权回路的图中，是可以得出d[v]&=d[u]+w(u，v)。
于是，就不难理解，在上述Bellman-Ford 算法中，&if d[v] & d[u]+w(u，v)，=& 包含负权回路，返回FASLE
else if =&不包含负权回路，返回TRUE。
ok，咱们，接下来，立马切入Dijkstra 算法。
三、深入浅出，彻底解剖Dijkstra 算法
I、松弛技术RELAX的介绍
Dijkstra 算法使用了松弛技术，对每个顶点v&-V，都设置一个属性d[v]，用来描述从源点s到v的最短路径上权值的上界，
称为最短路径的估计。
首先，得用O（V）的时间，来对最短路径的估计，和对前驱进行初始化工作。
INITIALIZE-SINGLE-SOURCE(G,&s) &&for&each&vertex&v&&&V[G] &&&do&d[v]&&&& &&&&&[v]&&&NIL&&&&&&&d[s]&0 &&RELAX(u,&v,&w) &if&d[v]&&&d[u]&+&w(u,&v) &&then&d[v]&&&d[u]&+&w(u,&v) &&&&[v]&&&u&&&&&&&&&
II、Dijkstra 算法
此Dijkstra 算法分三个步骤，INSERT (第3行), EXTRACT-MIN (第5行), 和DECREASE-KEY(第8行的RELAX，调用此减小关键字的操作)。
DIJKSTRA(G,&w,&s) &&INITIALIZE-SINGLE-SOURCE(G,&s)&&&&&&S&&&&O &&Q&&&V[G]&&&&&&&&&&&&&&while&Q&&&&O &&&&do&u&&&EXTRACT-MIN(Q)&&&&&&&&&&S&&&S&&{u} &&&&&&for&each&vertex&v&&&Adj[u] &&&&&&&&&&&do&RELAX(u,&v,&w)&&&&&&&
四、Dijkstra 算法的运行时间
在继续阐述之前，得先声明一个问题，DIJKSTRA（G，w，s）算法中的第5行，EXTRACT-MIN(Q)，最小优先队列的具体实现。而Dijkstra 算法的运行时间，则与此最小优先队列的采取何种具体实现，有关。
最小优先队列三种实现方法：
1、利用从1至|V| 编好号的顶点，简单地将每一个d[v]存入一个数组中对应的第v项，如上述DIJKSTRA（G，w，s）所示，Dijkstra 算法的运行时间为O(V^2+E)。
2、如果是二叉/项堆实现最小优先队列的话，EXTRACT-MIN(Q)的运行时间为O(V*lgV)，所以，Dijkstra 算法的运行时间为O(V*lgV+E*lgV)，若所有顶点都是从源点可达的话，O（(V+E)*lgV）=O（E*lgV）。当是稀疏图时，则E=O(V^2/lgV)，此Dijkstra 算法的运行时间为O(V^2)。
3、采用斐波那契堆实现最小优先队列的话，EXTRACT-MIN(Q)的运行时间为O(V*lgV)，所以，此Dijkstra 算法的运行时间即为O(V*lgV+E)。
综上所述，此最小优先队列的三种实现方法比较如下：
当|V|&&|E|时，采用DIJKSTRA（G，w，s）+ FIB-HEAP-EXTRACT-MIN(Q)，即斐波那契堆实现最小优先队列的话，
优势就体现出来了。
五、Dijkstra 算法 + FIB-HEAP-EXTRACT-MIN(H)，斐波那契堆实现最小优先队列
由以上内容，我们已经知道，用斐波那契堆来实现最小优先队列，可以将运行时间提升到O（VlgV+E）。|V|个EXTRACT-MIN 操作，每个平摊代价为O（lgV），|E|个DECREASE-KEY操作的每个平摊时间为O（1）。
下面，重点阐述DIJKSTRA(G, w, s)中，斐波那契堆实现最小优先队列的操作。
由上，我们已经知道，DIJKSTRA算法包含以下的三个步骤：
INSERT (第3行), EXTRACT-MIN (第5行), 和DECREASE-KEY(第8行的RELAX)。
先直接给出Dijkstra 算法 + FIB-HEAP-EXTRACT-MIN(H)的算法：
DIJKSTRA(G,&w,&s) &&INITIALIZE-SINGLE-SOURCE(G,&s) &&S&&&&O &&Q&&&V[G]&&&&&while&Q&&&&O &&&&do&u&&&EXTRACT-MIN(Q)&&&&&&&&&&&S&&&S&&{u} &&&&&&&&for&each&vertex&v&&&Adj[u] &&&&&&&&&&&do&RELAX(u,&v,&w)&&&&FIB-HEAP-EXTRACT-MIN(H)&&&&&z&&&min[H] &&&if&z&&&NIL &&&&&&then&for&each&child&x&of&z &&&&&&&&&&&&&&&do&add&x&to&the&root&list&of&H &&&&&&&&&&&&&&&&&&p[x]&&&NIL &&&&&&&&&&&remove&z&from&the&root&list&of&H &&&&&&&&&&&if&z&=&right[z] &&&&&&&&&&&&&&then&min[H]&&&NIL &&&&&&&&&&&&&else&min[H]&&&right[z] &&&&&&&&&&&&&&&&&&CONSOLIDATE(H)&&& &&&&&&&&&&n[H]&&&n[H]&-&1 &return&z&
六、Dijkstra 算法 +fibonacci堆各项步骤的具体分析&
ok，接下来，具体分步骤阐述以上各个操作：
第3行的INSERT操作：
FIB-HEAP-INSERT(H,&x)&&&&&&degree[x]&&&0 &&&p[x]&&&NIL &&&child[x]&&&NIL &&&left[x]&&&x &&&right[x]&&&x &&&mark[x]&&&FALSE &&&concatenate&the&root&list&containing&x&with&root&list&H &&&if&min[H]&=&NIL&or&key[x]&&&key[min[H]] &&&&&&then&min[H]&&&x &&n[H]&&&n[H]&+&1&
第5行的EXTRACT-MIN操作：
FIB-HEAP-EXTRACT-MIN(H)&&&&&z&&&min[H] &&&if&z&&&NIL &&&&&then&for&each&child&x&of&z &&&&&&&&&&&&&&do&add&x&to&the&root&list&of&H &&&&&&&&&&&&&&&&&p[x]&&&NIL &&&&&&&&&remove&z&from&the&root&list&of&H &&&&&&&&&if&z&=&right[z] &&&&&&&&&&&&then&min[H]&&&NIL &&&&&&&&&&&else&min[H]&&&right[z] &&&&&&&&&&&&&&&CONSOLIDATE(H)&&&&&&&&&&&&n[H]&&&n[H]&-&1 &return&z &
下图是FIB-HEAP-EXTRACT-MIN 的过程示意图：
CONSOLIDATE(H) &&for&i&&&0&to&D(n[H]) &&&&&&&do&A[i]&&&NIL &&for&each&node&w&in&the&root&list&of&H &&&&&&&do&x&&&w &&&&&&&&&&d&&&degree[x]&&&&&&&&&&&&&&&&&&while&A[d]&&&NIL &&&&&&&&&&&&&&do&y&&&A[d]&&&&&& &&&&&&&&&&&&&&&&&if&key[x]&&&key[y] &&&&&&&&&&&&&&&&&&then&exchange&x&&-&&y &&&&&&&&&&&&&&&FIB-HEAP-LINK(H,&y,&x)&&&&&&&&&&&&&&&&A[d]&&&NIL &&&&&&&&&&&&&&d&&&d&+&1 &&&&&&&&&A[d]&&&x &&min[H]&&&NIL &&for&i&&&0&to&D(n[H]) &&&&&do&if&A[i]&&&NIL &&&&&&&&&&then&add&A[i]&to&the&root&list&of&H &&&&&&&&&&&&&&&if&min[H]&=&NIL&or&key[A[i]]&&&key[min[H]] &&&&&&&&&&&&&&&then&min[H]&&&A[i] &&FIB-HEAP-LINK(H,&y,&x)&&&&remove&y&from&the&root&list&of&H &make&y&a&child&of&x,&incrementing&degree[x] &&mark[y]&&&FALSE&
第8行的RELAX的操作，已上已经给出:
RELAX(u,&v,&w) &&if&d[v]&&&d[u]&+&w(u,&v) &&&&then&d[v]&&&d[u]&+&w(u,&v) &&&&&&&&[v]&&&u&&&&&&&&&
一般来说，在Dijkstra 算法中，DECREASE-KEY的调用次数远多于EXTRACT-MIN的调用，
所以在不增加EXTRACT-MIN 操作的平摊时间前提下，尽量减小DECREASE-KEY操作的平摊时间，都能获得对比二叉堆更快的实现。
以下，是二叉堆，二项堆，斐波那契堆的各项操作的时间复杂度的比较：
操作&&&&&&&&&&&&&&&&& 二叉堆(最坏)&&&&&& 二项堆(最坏)&&&& 斐波那契堆(平摊)
MAKE-HEAP&&&&&&& &T(1)&&&&&&&&&&&&&&&&& &T(1)&&&&&&&&&&&&&&& &T(1)
INSERT&&&&&&&&&&&&&& &T(lg n)&&&&&&&&&&&&& O(lg n)&&&&&&&&&&& &T(1)
MINIMUM&&&&&&&&&& &T(1)&&&&&&&&&&&&&&&&& O(lg n)&&&&&&&&&&&& &T(1)
EXTRACT-MIN&&&& &T(lg n)&&&&&&&&&&&&& &T(lg n)&&&&&&&&&&& O(lg n)
UNION&&&&&&&&&&&&&& &T(n)&&&&&&&&&&&&&&&&& O(lg n)&&&&&&&&&&& &T(1)
DECREASE-KEY&& &T(lg n)&&&&&&&&&&&& &T(lg n)&&&&&&&&&&&&& &T(1)
DELETE&&&&&&&&&&&&& &T(lg n)&&&&&&&&&&&&& &T(lg n)&&&&&&&&&&&& O(lg n)
斐波那契堆，日后会在本BLOG内，更进一步的深入与具体阐述。且同时，此文，会不断的加深与扩展。
原文链接：http://blog.csdn.net/v_JULY_v/archive//6182419.aspx
【编辑推荐】
【责任编辑： TEL：（010）】
关于的更多文章
IE浏览器不支持很多CSS属性是出了名的，即便在支持的部分中，也
随着云计算、物联网、大数据、移动互联网的大发展，你应该知道这些。
Hadoop Summit 2013 大会讲师 PPT 第二季重磅来袭！如
现在这天气到处都是高温，还是老老实实的呆在家里上网
、27日，在美国圣何塞举行的Hadoop Summit
本书按照国家人事部、信息产业部全国计算机技术与软件专业资格（水平）考试要求编写，内容紧扣《网络管理员考试大纲》。全书共分
51CTO旗下网站2358人阅读
啊哈算法（22）
前两节我们写了Floyd-Warshall算法和
Dijkstra算法
Floyd算法可以解决负权边，但是复杂度高。Dijkstra不能解决负权边（边的权值为负值）的图。Bellman-Ford算法非常简单，核心代码只有4行，并且可以完美的解决带有负权边的图：
内循环循环了m次（m为边的个数），意思是把所有的边都松弛一遍。u，v，w三个数组是用来记录边的信息。例如第i条边存储在u[i],v[i],w[i]中，表示从顶点u[i]到顶点v[i]这条边的权值为w[i].
求下图中1号顶点到其余所有顶点的最短路径。
用一个dis数组存储1号顶点到所有顶点的距离
第1轮至第4轮对所有边进行松弛之后：
只需要进行n-1（n为顶点数）轮就可以了。因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1条边。
最短路径肯定是一个不包含回路的简单路径，即最多n-1条边。
整个Bellman-Ford算法一句话概括：
对所有的边进行n-1次“松弛”操作。
输入数据：
运行结果：
Bellman-Ford算法还可以检测一个图是否含有负权回路，如果在进行n-1轮松弛之后，仍然可以继续松弛，那么次图必然存在负权回路。
Bellman-Ford算法的时间复杂度为O(NM),
我们还可以进行优化，Bellman-Ford算法经常会在未达到n-1轮松弛前就已经计算出最短路，n-1其实是最大值，因此添加一个一维数组用来备份数组dis，如果在新的一轮松弛中数组dis不变，则可以提前结束。
在每次松弛后，会有一些顶点已经求得了最短路，此后这些顶点的最短路估计值就会一直保持不变，不再受后续松弛的影响，但是每次还要判断是否需要松弛，这里浪费了时间，所以
需要：每次仅对最短路径估计值发生变化了的顶点的所有出边执行松弛操作。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：807153次
积分：11864
积分：11864
排名：第998名
原创：406篇
转载：89篇
评论：243条
文章：29篇
阅读：53179
文章：47篇
阅读：203721
文章：27篇
阅读：71520
文章：15篇
阅读：89790
文章：25篇
阅读：24190
文章：47篇
阅读：26841
文章：35篇
阅读：126526
(1)(4)(2)(3)(10)(9)(59)(59)(38)(45)(15)(104)(119)(23)(2)(3)数据结构：单源最短路径--Dijkstra算法
Dijkstra算法
单源最短路径
给定一带权图，图中每条边的权值是非负的，代表着两顶点之间的距离。指定图中的一顶点为源点，找出源点到其它顶点的最短路径和其长度的问题，即是单源最短路径问题。
Dijkstra算法
求解单源最短路径问题的常用方法是Dijkstra(迪杰斯特拉)算法。该算法使用的是贪心策略：每次都找出剩余顶点中与源点距离最近的一个顶点。
带权图G=，令S为已确定了最短路径顶点的集合，则可用V-S表示剩余未确定最短路径顶点的集合。假设V0是源点，则初始 S={V0}。用数组Distance表示源点V0到其余顶点的路径长度，用数组pre[i]表示最短路径序列上顶点i的前一个顶点。初始时，pre[i]都是源点的下标。接下来需重复两个步骤：
从当前Distance[i]找出最小的一个，记录其下标v=i，源点V0到顶点Vv的最短路径即已确定，把Vv加入S。更新源点到剩余顶点的最短路径长度。更新方法是：以上一步的顶点Vv为中间点，若Distance[v]+weight(v,i) 需要指出，Dijkstra算法求解的不仅是有向图，无向图也是可以的。下面给出一个完整的有向带权图的实例：
有向带权图
Dijkstra算法的求解过程
其中，INF是infinity无穷大的意思。
#define MAXWEIGHT 100
#ifdef INFINITY
#undef INFINITY
#define INFINITY 1000
class Graph
//邻接矩阵
Graph(int numV);
void createGraph(int numE);
//析构方法
//迪杰斯特拉算法
void Dijkstra(int);
//打印邻接矩阵
void printAdjacentMatrix();
//检查输入
bool check(int, int, int);
//构造函数，指定顶点数目
Graph::Graph(int numV)
//对输入的顶点数进行检测
while (numV &= 0)
cout && 顶点数有误！重新输入 ;
cin && numV;
this-&numV = numV;
//构建邻接矩阵，并初始化
matrix = new int*[numV];
for (i = 0; i & numV; i++)
matrix[i] = new int[numV];
for (i = 0; i & numV; i++)
for (j = 0; j & numV; j++)
if (i == j)
matrix[i][i] = 0;
matrix[i][j] = INFINITY;
void Graph::createGraph(int numE)
对输入的边数做检测
一个numV个顶点的有向图，最多有numV*(numV - 1)条边
while (numE & 0 || numE & numV*(numV - 1))
cout && 边数有问题！重新输入 ;
cin && numE;
this-&numE = numE;
int tail, head, weight,
cout && 输入每条边的起点(弧尾)、终点(弧头)和权值 &&
while (i & numE)
cin && tail && head &&
while (!check(tail, head, weight))
cout && 输入的边不正确！请重新输入
cin && tail && head &&
matrix[tail][head] =
Graph::~Graph()
for (i = 0; i & numV; i++)
delete[] matrix[i];
迪杰斯特拉算法
求指定顶点vertex到其它顶点的最短路径
不仅要得出最短路径长度，也要得到其序列
void Graph::Dijkstra(int vertex)
//最短路径序列中每个顶点的直接前驱
int *pre = new int[numV];
for (i = 0; i & numV; i++)
//顶点vertex到各个顶点的路径长度
int *Distance = new int[numV];
//初始化路径长度
for (i = 0; i & numV; i++)
Distance[i] = matrix[vertex][i];
//标记各个顶点最短路径找到与否
bool *find = new bool[numV];
memset(find, 0, numV);
find[vertex] =
count = 1, v =
while (count & numV)
d = INFINITY;
//确定一个最短距离
for (i = 0; i & numV; i++)
if (!find[i] && Distance[i] & d)
d = Distance[i];
//更新剩余顶点的前驱和最短距离
for (i = 0; i & numV; i++)
if (!find[i])
d = Distance[v] + matrix[v][i];
if (d & Distance[i])
Distance[i] =
//打印最短路径序列和其长度
for (i = 0; i & numV; i++)
if (Distance[i] == 0);
else if (Distance[i] == INFINITY)
cout && 顶点
&& vertex && 到顶点
&& i && 无路径！ &&
cout && 顶点
&& vertex &&
最短路径长度是
&& Distance[i]
，其序列是...;
s.push(v);
v = pre[v];
s.push(v);
} while (v!=vertex);
//打印最短路径序列
while (!s.empty())
cout && setw(3) && s.top();
//打印邻接矩阵
void Graph::printAdjacentMatrix()
cout.setf(ios::left);
cout && setw(7) &&
for (i = 0; i & numV; i++)
cout && setw(7) &&
for (i = 0; i & numV; i++)
cout && setw(7) &&
for (j = 0; j & numV; j++)
cout && setw(7) && matrix[i][j];
bool Graph::check(int tail, int head, int weight)
if (tail & 0 || tail &= numV || head & 0 || head &= numV
|| weight &= 0 || weight &= MAXWEIGHT)
int main()
cout && ******Dijkstra***by David*** &&
int numV, numE;
cout && 建图... &&
cout && 输入顶点数 ;
cin && numV;
Graph graph(numV);
cout && 输入边数 ;
cin && numE;
graph.createGraph(numE);
cout && endl && Dijkstra... &&
for (int i = 0; i & numV; i++)
graph.Dijkstra(i);
system(pause);
完整代码下载：Dijkstra算法
若有所帮助，顶一个哦！
专栏目录：
数据结构与算法c指针
(window.slotbydup=window.slotbydup || []).push({
id: '2467140',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467142',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'