92804人阅读
数据结构与算法（12）
1.dijkstra算法简介
Dijkstra算法是由E.W.Dijkstra于1959年提出，又叫迪杰斯特拉算法，它应用了贪心算法模式，是目前公认的最好的求解最短路径的方法。算法解决的是有向图中单个源点到其他顶点的最短路径问题，其主要特点是每次迭代时选择的下一个顶点是标记点之外距离源点最近的顶点。但由于dijkstra算法主要计算从源点到其他所有点的最短路径，所以算法的效率较低。
2.dijkstra算法基本过程
假设路网中每一个节点都有标号&是从出发点s到点t的最短路径长度；表示从s到t的最短路径中t点的前一个点。求解从出发点s到点t的最短路径算法的基本过程为：
1.&&&&&&初始化。出发点设置为：
标记起源点s，记k = s,其他所有点设为未标记。
2.&&&&&&检验从所有已标记的点k到其他直接连接的未标记的点j的距离，并设置:
3.&&&&&&选取下一个点。从所有未标记的点中选取 最小的点i，点i被选为最短路径中的一点，并设为已标记的。
4.&&&&&&找到点i的前一点。从已经标记的点集合中找到直接连接到点i的点,并标记为 。
5.&&&&&&标记点i。如果所有的点已标记，则算法结束。否则，记k = i，转到2继续。
从以上算法的步骤中可以看出 ：dijkstra算法的关键部分是从未标记的点中不断地找出距离源点距离最近的点，并把改点加入到标记的点集合中，同时更新未标记的点集合中其余点到起始点的最短估计距离&。
以一个带有权值的无向图为例，用dijkstra算法分析从源点A到目标点F的最短路径。
1. 用带有权值的一个矩阵w表示含有n各节点的带权无向图， 代表弧段 的权值，如果从节点 到节点 不连通，那么 ，带权值图邻接矩阵如下图所示.设置A为源点,G为目的点, 代表从节点A到有向图中其他节点 的最短路径长度。设置初始值
代表标记的节点集合。
2. 是从A点出发求出的一条最短路径上的终止节点，令 ；
3. &修改起始节点A到集合之间的最短路径的长度值，如果d(j)+w(j,k) & d(k)，那么d(k) = d(j) + w(j,k)；
4. 重复步骤2、3的操作N-1次，最终得到从起始节点A到其他节点的最短路径，按照递增的顺序排列路径的长度。
3.dijkstra算法的流程图如下所示：
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1273860次
积分：11975
积分：11975
排名：第1126名
原创：256篇
转载：57篇
评论：315条
文章：40篇
阅读：157128
文章：48篇
阅读：72628
文章：24篇
阅读：60355
(3)(2)(1)(1)(1)(9)(2)(6)(1)(4)(6)(1)(3)(5)(4)(3)(7)(12)(11)(1)(14)(7)(1)(1)(5)(4)(39)(15)(5)(5)(10)(5)(8)(7)(2)(1)(7)(19)(29)(35)(2)(7)(1)(1)(2)
Makefile 学习图论之最短路径（6）
本周来来介绍指定一个点（源点）到其余各个顶点的最短路径，也叫做“单源最短路径”。例如求下图中的1号顶点到2、3、4、5、6号顶点的最短路径。
& && &&&与Floyd-Warshall算法一样这里仍然使用二维数组e来存储顶点之间边的关系，初始值如下。
& && &&&我们还需要用一个一维数组dis来存储1号顶点到其余各个顶点的初始路程，如下。
& && &&&我们将此时dis数组中的值称为最短路的“估计值”。
& && &&&既然是求1号顶点到其余各个顶点的最短路程，那就先找一个离1号顶点最近的顶点。通过数组dis可知当前离1号顶点最近是2号顶点。当选择了2号顶点后，dis[2]的值就已经从“估计值”变为了“确定值”，即1号顶点到2号顶点的最短路程就是当前dis[2]值。为什么呢？你想啊，目前离1号顶点最近的是2号顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得1号顶点到2号顶点的路程进一步缩短了。因为1号顶点到其它顶点的路程肯定没有1号到2号顶点短，对吧O(∩_∩)O~
& && &&&既然选了2号顶点，接下来再来看2号顶点有哪些出边呢。有2-&3和2-&4这两条边。先讨论通过2-&3这条边能否让1号顶点到3号顶点的路程变短。也就是说现在来比较dis[3]和dis[2]+e[2][3]的大小。其中dis[3]表示1号顶点到3号顶点的路程。dis[2]+e[2][3]中dis[2]表示1号顶点到2号顶点的路程，e[2][3]表示2-&3这条边。所以dis[2]+e[2][3]就表示从1号顶点先到2号顶点，再通过2-&3这条边，到达3号顶点的路程。
& && &&&我们发现dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]&dis[2]+e[2][3]，因此dis[3]要更新为10。这个过程有个专业术语叫做“松弛”。即1号顶点到3号顶点的路程即dis[3]，通过2-&3这条边松弛成功。这便是Dijkstra算法的主要思想：通过“边”来松弛1号顶点到其余各个顶点的路程。
& && &&&同理通过2-&4（e[2][4]），可以将dis[4]的值从∞松弛为4（dis[4]初始为∞，dis[2]+e[2][4]=1+3=4，dis[4]&dis[2]+e[2][4]，因此dis[4]要更新为4）。
& && &&&刚才我们对2号顶点所有的出边进行了松弛。松弛完毕之后dis数组为：
& && &&&接下来，继续在剩下的3、4、5和6号顶点中，选出离1号顶点最近的顶点。通过上面更新过dis数组，当前离1号顶点最近是4号顶点。此时，dis[4]的值已经从“估计值”变为了“确定值”。下面继续对4号顶点的所有出边（4-&3，4-&5和4-&6）用刚才的方法进行松弛。松弛完毕之后dis数组为：
& && &&&继续在剩下的3、5和6号顶点中，选出离1号顶点最近的顶点，这次选择3号顶点。此时，dis[3]的值已经从“估计值”变为了“确定值”。对3号顶点的所有出边（3-&5）进行松弛。松弛完毕之后dis数组为：
& && &&&继续在剩下的5和6号顶点中，选出离1号顶点最近的顶点，这次选择5号顶点。此时，dis[5]的值已经从“估计值”变为了“确定值”。对5号顶点的所有出边（5-&4）进行松弛。松弛完毕之后dis数组为：
& && &&&最后对6号顶点所有点出边进行松弛。因为这个例子中6号顶点没有出边，因此不用处理。到此，dis数组中所有的值都已经从“估计值”变为了“确定值”。
& && &&&最终dis数组如下，这便是1号顶点到其余各个顶点的最短路径。
& && &&&OK，现在来总结一下刚才的算法。算法的基本思想是：每次找到离源点（上面例子的源点就是1号顶点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。基本步骤如下：
将所有的顶点分为两部分：已知最短路程的顶点集合P和未知最短路径的顶点集合Q。最开始，已知最短路径的顶点集合P中只有源点一个顶点。我们这里用一个book[ i ]数组来记录哪些点在集合P中。例如对于某个顶点i，如果book[ i ]为1则表示这个顶点在集合P中，如果book[ i ]为0则表示这个顶点在集合Q中。设置源点s到自己的最短路径为0即dis=0。若存在源点有能直接到达的顶点i，则把dis[ i ]设为e[s][ i ]。同时把所有其它（源点不能直接到达的）顶点的最短路径为设为∞。在集合Q的所有顶点中选择一个离源点s最近的顶点u（即dis[u]最小）加入到集合P。并考察所有以点u为起点的边，对每一条边进行松弛操作。例如存在一条从u到v的边，那么可以通过将边u-&v添加到尾部来拓展一条从s到v的路径，这条路径的长度是dis[u]+e[u][v]。如果这个值比目前已知的dis[v]的值要小，我们可以用新值来替代当前dis[v]中的值。重复第3步，如果集合Q为空，算法结束。最终dis数组中的值就是源点到所有顶点的最短路径。
& && &&&完整的Dijkstra算法代码如下：
#include &stdio.h&
int main()
int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,
int inf=; //用inf(infinity的缩写)存储一个我们认为的正无穷值
//读入n和m，n表示顶点个数，m表示边的条数
scanf(&%d %d&,&n,&m);
for(i=1;i&=n;i++)
for(j=1;j&=n;j++)
if(i==j) e[i][j]=0;
else e[i][j]=
for(i=1;i&=m;i++)
scanf(&%d %d %d&,&t1,&t2,&t3);
e[t1][t2]=t3;
//初始化dis数组，这里是1号顶点到其余各个顶点的初始路程
for(i=1;i&=n;i++)
dis[i]=e[1][i];
//book数组初始化
for(i=1;i&=n;i++)
book[i]=0;
book[1]=1;
//Dijkstra算法核心语句
for(i=1;i&=n-1;i++)
//找到离1号顶点最近的顶点
for(j=1;j&=n;j++)
if(book[j]==0 && dis[j]&min)
min=dis[j];
book[u]=1;
for(v=1;v&=n;v++)
if(e[u][v]&inf)
if(dis[v]&dis[u]+e[u][v])
dis[v]=dis[u]+e[u][v];
//输出最终的结果
for(i=1;i&=n;i++)
printf(&%d &,dis[i]);
getchar();
getchar();
通过上面的代码我们可以看出，这个算法的时间复杂度是O(N*2*N)即O(N2)。其中每次找到离1号顶点最近的顶点的时间复杂度是O(N)，这里我们可以用“堆”（以后再说）来优化，使得这一部分的时间复杂度降低到O(logN)。另外对于边数M少于N2的稀疏图来说（我们把M远小于N2的图称为稀疏图，而M相对较大的图称为稠密图），我们可以用邻接表（这是个神马东西？不要着急，下周再仔细讲解）来代替邻接矩阵，使得整个时间复杂度优化到O(MlogN)。请注意！在最坏的情况下M就是N2，这样的话MlogN要比N2还要大。但是大多数情况下并不会有那么多边，因此MlogN要比N2小很多。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：94196次
积分：4250
积分：4250
排名：第6670名
原创：312篇
转载：65篇
评论：16条
(16)(22)(51)(54)(28)(26)(24)(47)(57)(33)(19)(2)(1)(1)迪杰斯特拉算法解析 - 推酷
迪杰斯特拉算法解析
一.理论基础
迪杰斯特拉算法（下文简称DJ算法）是理论基础是一条简单的定理：
下一条最短路径或者是弧(V0, Vx)，或者是中间经过S中的某些顶点，而后到达Vx的路径。（S是最短路径已知的顶点集合）
（为了准确的描述定理，这里就直接摘抄了。。至于它对不对，嗯，据说反证法可证之）很明显这是一个递推算法：反复求下一条，直至没有下一条为止。
二.问题分析
现有加权有向图如下：
求从V0出发，到达其它各个顶点的最短路径。
首先为了把它转换成便于描述的数学形式，得写出对应的邻接矩阵（x表示不可达）：
分析定理可以得出：目前S集合中只有1个顶点：V0（V0到自身的肯定是最短路径），除了S集合这个辅助空间外，我们还需要：
V集合：最短路径未知的顶点组成的集合，即S集合的补集
path[]：记录最短路径，用来显示结果
dist[]：记录路径长度，作用同上
Vx：记录下一个顶点
准备工作结束，可以开始求解了
三.求解过程
0.初始状态
dist[]初始化为V0到各个顶点的直接距离（x表示不可直达），path[]初始化为对应的路径，不可直达的记作NULL，选取V集合中dist值最小的顶点V2作为下一个顶点（定理中的Vx）
把V2加入S集合，我们多了一个中转站V2，接下来更新dist[]，看借助V2中转的话是不是更短，根据计算结果更新dist[]和path[]，把更短的路径长度和对应路径放进去，V集合中dist值最小的V3作为下一个顶点
继续选取下一个顶点，直至V集合中没有可选顶点为止
DJ算法过程非常简单：
确定S中的第一个点（也就是源点V0）；
根据定理递推（一直找最短，并试图借助最短中转）
算法思路本身不难，当初看不明白是因为被具体的伪代码实现绕进去了，所以学习算法应该关注思路而不是具体实现，尤其是伪代码算法，通常会随意声明一些奇怪的数据结构，却不解释为什么需要这些辅助空间，比如本例中，S集合和V集合只需要有一个即可，path[]和dist[]也可以用结构体清晰的表示出来，但伪代码中零零散散的全都用到了，过多的辅助空间反而妨碍了理解算法本身。
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致> 迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路
master & &
发布时间： & &
浏览：16 & &
回复：0 & &
悬赏：0.0希赛币
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于（）策略的算法。
A．分治&&&
B．动态规划&&&
C．贪心&&&
所属试卷：
本问题标题：
本问题地址：
温馨提示：本问答中心的任何言论仅代表发言者个人的观点，与希赛网立场无关。请对您的言论负责，遵守中华人民共和国有关法律、法规。如果您的言论违反希赛网问答中心的规则，将会被删除。
暂无合适的专家
&&&&&&&&&&&&&&&
希赛网 版权所有 & &&