摘要
通过对《图论及其算法》深入的学习，本文简单介绍了图论的发展与特点，阐述了最短路径问题及其算法。并采用迪克斯屈拉算法解决最短路由问题。众所周知，图论是数学的一个分支，它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这些图形通常用来描述某些事物之间的特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有的关系。最短路由的问题利用了图的描述，并把算法用C++语言来实现，这就很好地将所学知识和现实生活结合起来。
关键词：最短路径 Dijkstra算法 C++
Abstract
Based on the graph theory and algorithm of in-depth study, this paper briefly introduces the development and characteristics of graph theory, presents the shortest path problem and its algorithm, and adopts Dijkstra algorithm to solve the shortest routing problem. As is known to all, graph theory is a branch of mathematics, it so as the research object. Graph theory in the diagram consists in some given points and the lines connecting two points of a graph, these graphics are usually used to describe the specific relationship between things, using points representative things, using the lines connecting two points representative the corresponding relationship between things. The shortest routing problem makes use of graph description, and the realization of the algorithm, which takes advantage of C++. it is a good way to combine the knowledge we’ve learned with our life.
Keyword:shortest path Dijkstra's algorithm C++
引言
随着现代通信技术的不断发展，通信网的范围也逐渐扩大，通信网已成为人们生活中不可或缺的一部分了。而随着人们之间通信次数的增加，使的通信网的通信量也随之大量增加。这给通信网带了沉重的负担。如何在现有通信网的基础上提高通信效率，网络利用率和网络可靠性[1]，以满足人们日益增长的对网络通信能力的需求已成为对通信网研究的主要内容。迪克斯屈拉算法是最适合解决网络拓扑中两节点间的最短通信距离的问题的方法之一。本文就如何利用迪克斯屈拉算法解决网络中点到点通信的最短距离问题做了说明，以此提高通信网的通信效率。
第一章迪克斯屈拉算法
1.1算法介绍
Dijkstra(迪克斯屈拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边[3]。
Procedure Dijkstra（G：所有权都为正数的加权连通简单图）
{G带有定点a=v
0, v
1
……，v
n
=z和权w（v
i
, v
j
）,若{ v
i
, v
j
}不是G中的
边，则w（v
i , v
j
）=∞}
For i:=1 to n
L（vi）:=∞
L（a）: =0
S:=φ
{初始化标记，a的标记为0，其余结点标记为∞，S是空集}
While z S
begin
u:=不属于S的L（u）最小的一个顶点
S：=S{u}
for 所有不属于S的顶点v
if L(u)+w(u,v) < L(v)
then L(v):=L(u)+w(u,v)
{这样就给S中添加带最小标记的顶点并且更新不在S中的顶点标记} end {L（z）=从a到z的最短路的长度}
1.2根据Dijkstra算法给出的定理
定理 1 迪克斯屈拉算法求出连通简单无向加权图中的两个顶点之间最短路
的长度[2]。
迪克斯屈拉算法通过一步一步的迭代求出最短路径，假设在第k次迭代中。在s中的顶点v的标记L(v)是从a到这个顶点v的最短路的长度。不在s中的顶点的标记是（除了这个顶点自身之外）只经过s中顶点的从a到这个顶点的最短路的长度。设u是第k次迭代结束时带最小标记的不在s中的顶点（若该顶点不唯一，可采用带最小标记的任意顶点）。在第k+1次迭代中，u是添加到s中的顶点，则在第k+1次迭代中，u的标记必须是a到u的最短路的长度。否则，k次迭代后，从结点a到某个结点l的路，其路得长度小于L
k
（v）。
定理2 迪克斯屈拉算法使用O（n2）次运算（加法和比较）来求出n阶连通简单无向加权图中两个顶点之间最短路的长度,求加权无向图中最短路的Dijkstra算法可以推广到求加权有向图中最短有向路。
定理3 设有向图G中不含长度非正的有向圈，并且从点1到其余各点都有
有限长的有向路,那么G中结点1到其余各点j的最短有向路长度S
j
有唯一有限
解{S
j
}。
定理4 设S
j
是加权有向图G中自结点1到结点j的最短有向路的长度，并
且对所有的j=1，2，3，……，n，S
j
为有限值。若图G中除结点1外的其余各点能重新编写成如下的序号2，3，……，n使得对所有i S i ≤S j 且w 或者S i >S j 且 w 定理5设G= Dijkstra算法求出了图中一个特定顶点到其他各定点的最短路，可以利用Dijkstra算法解决实际生活中的一些问题。 第二章 Dijkstra算法的实际应用 2.1 问题的提出 在现实生活中，我们常常会遇到很多问题，都是要找到一个地方到另一个地方的最短路径，当然还要满足各方面的要求，包括可实现性、预算、带来的利益等各方面条件[4]。比如Dijkstra算法在计算机网络路由问题中的应用。通常我们解决的办法就是找到一条距离最短，又在现实可接受范围内的路径。 2.2 运用Dijkstra算法解决实际问题 在通信网中，如何利用现有的通信网络，通过最短的通信路径完成信息的传递，在通信网研究中具有重要意义。为了降低研究复杂性，我们假设每条通信线路的通信系能和状况都一样且恒定不变。建立如下网络模型：点用来表示路由节点（用a到e及z…表示），边用来表示两节点间的通信线路，边上的权重表示两节点间的距离，节点本身到他自己的距离记为0，如果两节点没有边直接相连用∞表示。 a 图1 无向图G 利用Dijkstra算法实现求解最短路径问题要有边权。本文最佳路径是基于两个路由节点间的距离。因此找路由节点间的最短距离就转化成了找图G=（V,E）中指定两点间的最小距离了。 首先我们利用上图可以知道节点之间的邻接关系，为此我们可以先画出节点间的邻接矩阵，方便我们对节点的关系进行了解。如下表（单位：m）： 下面对最优路径进行分析，我们a为路径的起点，z为终点。 初始化： L(a)=0 L(b)=∞，L(c)=∞，L(d)=∞，L(e)=∞，L(z)=∞， S=Φ, 一次迭代：U=a，S={a} L(a)+W(a,b)=0+400=400 L(a)+W(a,c)=0+200=200 L(a)+W(a,d)=0+∞=∞ L(a)+W(a,e)=0+∞=∞ L(a)+W(a,z)=0+∞=∞ L(b)=400, L(c)=200, L(d)= L(e)= L(z)= ∞ 二次迭代：U=c，S={a,c} L(c)+W(c,b)=200+100=300 L(c)+W(c,d)=200+800=1000 L(c)+W(c,e)=200+1000=1200 L(c)+W(c,z)=200+∞=∞ L(b)=300， L(d)=1000， L(e)=1200，L(z)= ∞ 三次迭代：U=b，S={a，c，b} L(b)+W(b,d)=300+500=800 L(b)+W(b,e)=300+∞=∞> ∞ L(b)+W(b,z)=300+∞=∞ L(d)=800， L(e)=1200, L(z)= ∞ 四次迭代：U=d，S={a，c，b，d} L(d)+W(d,e)=800+200=1000 L(d)+W(d,z)=800+600=1400 L(e)=1000， L(z)=1400 五次迭代：U=e，S={a，c，b，d，e} L(e)+W(e,z)=1000+300=1300 L(z)=1300 结束：U=z，S={a，c，b，d，e，z} 由于终点z已经进入S集合中所以迭代结束。这样就找到了从起点a到终点z的最短路径以及到中间各点的最短路径。 本文的算法是在VC++的环境下实现的，程序的基本思想是基于Dijkstra算法的。这个程序中是以节点1代表a，且以节点1作为初始节点，节点6最为终止节点，在程序中所求的最短路径问题则为从节点1到节点6以及其他中间节点的最短路径[5]。具体的程序代码见附录。 图2运行结果 第三章结论 通过本学期对《图论及其算法》的学习，使我深刻体会到了图论在实际生活中的广泛应用，也使从以前的定向思维上升了一个台阶，学会把抽象的变为具体，能用点、线、图来描述抽象的事物，把很多抽象的知识具体化，使得抽象的知识更容易理解、记忆。 《图论及其算法》中有很多简便的算法，可以实现很多功能。Dijkstra算法是图论众多算法中的一种，能够方便的找到两点之间的最短路径，通过上面Dijkstra算法的应用例子可以清楚的看到通过Dijkstra算法可以在很复杂的图中很容易的找到点到点的最短路径，也可以对实际生活中的一些问题给予很大的帮助。 参考文献 [1] 乐阳,龚健雅;Dijkstra最短路径算法的一种高效率实现[J];武汉测绘科技 大学学报;1999年03期. [2] 殷剑宏，吴开亚；《图论及其算法》，中国科学技术大学出版社；2005. [3] 王树禾.图论[M].北京：科学出版社.2009. [4] 凡金伟,吕康.基于Dijkstra算法在物流配送中的应用[J].电脑编程技巧与 维护,2009,(04). [5] 徐凤生，李天志.所有最短路径的求解算法[J].微计算机应用，2004，25（3）： 295-300. 附录 #include #include #define MaxNum 10000 //节点间不是邻居节点 #define n 6//节点数目 int dist[100]; //到节点1的最短路径值 int state[100]={0}; //节点被搜索过状态指示 int data[100][100]; //邻接矩阵 int path[100];//从起点到终点的最短路径，0为没在集合，从1开始 int indexflag=1; //查找权值最小的节点 int first=1; //起点 int end=7; //终点 int findmin() { int minnode=0, min=MaxNum; for(int i=1; i<=n; i++) if ((dist[i] min=dist[i]; minnode=i; } return minnode; } void main() { long int data[n+1][n+1]= { {0,0,0,0,0,0,0,}, {0,0,400,200,10000,10000,10000}, {0,400,0,100,500,10000,1000}, {0,200,100,0,800,1000,10000}, {0,10000,500,800,0,200,600}, {0,10000,10000,1000,200,0,300}, {0,10000,10000,10000,600,300,0} }; /*初始化*/ for(int i=1; i<=n; i++) { dist[i]=data[1][i]; path[i]=0; } state[first]=1; int done=1; while (done { int node=findmin(); if (node!=0) { done++; //找到一个点就加1 state[node]=1; //标记已经找到了从节点1到节点node的最短路径 path[indexflag]=node; indexflag++; for(int i=1; i<=n; i++)//更新还没有找到的点的路径值 if ((dist[i]>dist[node]+data[node][i]) && (!state[i])) dist[i]=dist[node]+data[node][i]; if(node==end) break; } else break; } for(int p=1; p<=n; p++) //输出最短路径 { if (dist[p]==MaxNum) cout<<"从first点没有到"< else cout<<"从first点到"< } cout< cout<<"从first点到end点的最短路径为："; for(int index=1;index { cout<<"->"< } } 两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。 以各城镇为图G 的顶点，两城镇间的直通铁路为图G 相应两顶点间的边，得图G 。对G 的每一边e ，赋以一个实数)(e w —直通铁路的长度，称为e 的权，得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点00,v u 间的具最小权的轨。这条轨叫做00,v u 间的最短路，它的权叫做00,v u 间的距离，亦记作),(00v u d 。 求最短路已有成熟的算法：迪克斯特拉（Dijkstra ）算法，其基本思想是按距0u 从近到远为顺序，依次求得0u 到G 的各顶点的最短路和距离，直至0v （或直至G 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。 (i) 令0)(0=u l ，对0u v ≠，令∞=)(v l ，}{00u S =，0=i 。 (ii) 对每个i S v ∈（i i S V S \=），用 )}()(),({min uv w u l v l i S u +∈ 代替)(v l 。计算)}({min v l i S v ∈，把达到这个最小值的一个顶点记为1+i u ，令}{11++=i i i u S S 。 (iii). 若1||-=V i ，停止；若1||- 5.3.4 附录E 最短路径算法——Dijkstra 算法 在路由选择算法中都要用到求最短路径算法。最出名的求最短路径算法有两个，即Bellman-Ford 算法和Dijkstra 算法。这两种算法的思路不同，但得出的结果是相同的。我们在下面只介绍Dijkstra 算法，它的已知条件是整个网络拓扑和各链路的长度。 应注意到，若将已知的各链路长度改为链路时延或费用，这就相当于求任意两结点之间具有最小时延或最小费用的路径。因此，求最短路径的算法具有普遍的应用价值。 令v 部分： 不直接相连与结点若结点 1 v ? ?∞在用计算机进行求解时，可以用一个比任何路径长度大得多的数值代替∞。对于上述例子， 可以使D (v ) = 99。 (2) 寻找一个不在N 中的结点w ，其D (w )值为最小。把w 加入到N 中。然后对所有不在N 中的结点v ，用[D (v ), D (w ) + l (w , v )]中的较小的值去更新原有的D (v )值，即： D (v )←Min[D (v ), D (w ) + l (w , v )] (E-1) (3) 重复步骤(2)，直到所有的网络结点都在N 中为止。 表E-1是对图E-1的网络进行求解的详细步骤。可以看出，上述的步骤(2)共执行了5次。表中带圆圈的数字是在每一次执行步骤(2)时所寻找的具有最小值的D (w ) 值。当第5次执行步骤(2)并得出了结果后，所有网络结点都已包含在N 之中，整个算法即告结束。 表E-1 计算图E-1的网络的最短路径 现在我们对以上的最短路径树的找出过程进行一些解释。 因为选择了结点1为源结点，因此一开始在集合N中只有结点1。结点1只和结点2, 3和4直接相连，因此在初始化时，在D(2)，D(3)和D(4)下面就填入结点1到这些结点相应的距离，而在D(5)和D(6)下面填入∞。 下面执行步骤1。在结点1以外的结点中，找出一个距结点1最近的结点w，这应当是w = 4，因为在D(2)，D(3)和D(4)中，D(4) = 1，它的之值最小。于是将结点4加入到结点集合N中。这时，我们在步骤1这一行和D(4)这一列下面写入①，数字1表示结点4到结点1的距离，数字1的圆圈表示结点4在这个步骤加入到结点集合N中了。 接着就要对所有不在集合N中的结点（即结点2, 3, 5和6）逐个执行（E-1）式。 对于结点2，原来的D(2) = 2。现在D(w) + l(w, v) = D(4) + l(4, 2) = 1 + 2 = 3 > D(2)。因此结点2到结点1距离不变，仍为2。 对于结点3，原来的D(3) = 5。现在D(w) + l(w, v) = D(4) + l(4, 3) = 1 + 3 = 4 < D(3)。因此结点3到结点1的距离要更新，从5减小到4。 对于结点5，原来的D(5) = ∞。现在D(w) + l(w, v) = D(4) + l(4, 5) = 1 + 1 = 2 < D(5)。因此结点5到结点1的距离要更新，从∞减小到2。 对于结点6，现在到结点1的距离仍为∞。 步骤1的计算到此就结束了。 下面执行步骤2。在结点1和4以外的结点中，找出一个距结点1最近的结点w。现在有两个结点（结点2和5）到结点1的距离一样，都是2。我们选择结点5（当然也可以选择结点2，最后得出的结果还是一样的）。以后的详细步骤这里就省略了，读者可以自行完 1的路由表。此路由表指出对于发往某个目的结点的分组，从结点1发出后的下一跳结点（在算法中常称为“后继结点”）和距离。当然，像这样的路由表，在所有其他各结点中都有一个。但这就需要分别以这些结点为源结点，重新执行算法，然后才能找出以这个结点为根的最短路径树和相应的路由表。 迪克斯特拉算法： 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。 定义： Dijkstra算法一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。 算法思想： 按路径长度递增次序产生算法： 把顶点集合V分成两组： （1）S：已求出的顶点的集合（初始时只含有源点V0） （2）V-S=T：尚未确定的顶点集合 将T中顶点按递增的次序加入到S中，保证： （1）从源点V0到S中其他各顶点的长度都不大于从V0到T 中任何顶点的最短路径长度 （2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的长度 T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度 依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。 （反证法可证） 求最短路径步骤 算法步骤如下： G={V,E} 1.初始时令S={V0},T=V-S={其余顶点}，T中顶点对应的距离值 若存在 5.3.4 附录E 最短路径算法——Dijkstra算法 在路由选择算法中都要用到求最短路径算法。最出名的求最短路径算法有两个，即Bellman-Ford算法和Dijkstra算法。这两种算法的思路不同，但得出的结果是相同的。我们在下面只介绍Dijkstra算法，它的已知条件是整个网络拓扑和各链路的长度。 应注意到，若将已知的各链路长度改为链路时延或费用，这就相当于求任意两结点之间具有最小时延或最小费用的路径。因此，求最短路径的算法具有普遍的应用价值。 下面以图E-1的网络为例来讨论这种算法，即寻找从源结点到网络中其他各结点的最短路径。为方便起见，设源结点为结点1。然后一步一步地寻找，每次找一个结点到源结点的最短路径，直到把所有 点1, j)为结点i (1) 初始化 令N表示网络结点的集合。先令N = {1}。对所有不在N中的结点v，写出 不直接相连与结点若结点直接相连 与结点若结点 1 1 ),1()(v v v l v D ? ? ?∞= 在用计算机进行求解时，可以用一个比任何路径长度大得多的数值代替∞。对于上述例子，可以使D (v ) = 99。 (2) 寻找一个不在N 中的结点w ，其D (w )值为最小。把w 加入到N 中。然后对所有不在N 中的结点v ，用[D (v ), D (w ) + l (w , v )]中的较小的值去更新原有的D (v )值，即： D (v )←Min[D (v ), D (w ) + l (w , v )] (E-1) (3) 重复步骤(2)，直到所有的网络结点都在N 中为止。 表E-1是对图E-1的网络进行求解的详细步骤。可以看出，上述的步骤(2)共执行了5次。表中带圆圈的数字是在每一次执行步骤(2)时所寻找的具有最小值的D (w ) 值。当第5次执行步骤(2)并得出了结果后，所有网络结点都已包含在N 之中，整个算法即告结束。 表E-1 计算图E-1的网络的最短路径 最短路径之Dijkstra算法详细讲解 １最短路径算法 在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括： （１）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 （２）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 （３）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 （４）全局最短路径问题：求图中所有的最短路径。 用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。 本文主要研究Dijkstra算法的单源算法。 ２Dijkstra算法 2.1Dijkstra算法 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 2.2Dijkstra算法思想 Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径,就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U 表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S 中的顶点为中间顶点的当前最短路径长度。 2.3Dijkstra算法具体步骤 最短路径—Dijkstra算法 Dijkstra算法 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。 问题描述：在无向图G=(V,E) 中，假设每条边E[i] 的长度为w[i]，找到由顶点V0 到其余各点的最短路径。（单源最短路径） 2.算法描述 1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S 中只有一个源点，以后每求得一条最短路径, 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 2)算法步骤： a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边， 则 Dijkstra 算法 #include "stdio.h" #include "stdlib.h" #define M 10000 int dist[M] = {0},fa[M] = {0},visit[M] = {0}; int g[M][M] = {0}; int n,start,end; int findmin(){ int i,flag; int min = 987654321; for( i = 1 ; i<= n ; i++ ) if( visit[i] == 0 && dist[i] < min && dist[i] != 0){ min = dist[i]; flag = i; } return flag; } int Dijkstra(){ int i,j,pos; for( i = 1 ; i <= n ; i++ ){ dist[i] = g[start][i]; if( dist[i] == 123456789 ) fa[i] = i; else fa[i] = start; } visit[start] = 1; for( i = 1 ; i <= n ; i++ ){ pos = 0; pos = findmin(); if(pos == 0) break; visit[pos] = 1; for( j = 1 ; j <= n ; j++ ) if( visit[j] == 0 && dist[j] > dist[pos] + g[pos][j] ){ dist[j] = dist[pos] + g[pos][j]; fa[j] = pos; } } } int main(){ int i,j; int p; scanf("%d%d%d",&n,&start,&end); for( i = 1 ; i <= n ; i++ ) D i j k s t r a算法详细讲解 This model paper was revised by the Standardization Office on December 10, 2020 最短路径之D i j k s t r a算法详细讲解 １最短路径算法 在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括： （１）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 （２）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 （３）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 （４）全局最短路径问题：求图中所有的最短路径。 用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。 本文主要研究Dijkstra算法的单源算法。 ２ Dijkstra算法 2.1 Dijkstra算法 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 2.2 Dijkstra算法思想 Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 2.3 Dijkstra算法具体步骤 Dijkstra算法原理详细讲解 如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等） 算法执行步骤如下表： Dijkstra算法的完整实现版本之算法的源代码 样例图: 输入格式: 输出格式: 输入时，将s,t,x,y,z五个点按照1,2,3,4,5起别名，输入格式按照下图例所示当提示Please enter the vertex where Dijkstra algorithm starts:时输入算法的起 始点 比如计算结果v1v4v2表示从点1到点2经过1，4，2为最短路径 Dijkstra算法的完整实现版本，算法的源代码 /* Dijkstra.c Copyright (c) 2002, 2006 by ctu_85 All Rights Reserved. */ #include "stdio.h" #include "malloc.h" #define maxium 32767 #define maxver 9 /*defines the max number of vertexs which the programm can handle*/ #define OK 1 struct Point { char vertex[3]; struct Link *work; struct Point *next; }; struct Link { char vertex[3]; int value; struct Link *next; }; struct Table /*the workbannch of the algorithm*/ { int cost; int Known; char vertex[3]; 最短路径之Dijkstra算法详细讲解１最短路径算法 在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括： （１）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 （２）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 （３）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 （４）全局最短路径问题：求图中所有的最短路径。 用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。 本文主要研究Dijkstra算法的单源算法。 ２ Dijkstra算法 2.1 Dijkstra算法 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 2.2 Dijkstra算法思想 Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 2.3 Dijkstra算法具体步骤 Dijkstra算法描述 目录 一、算法概述 (2) 二、算法原理及计算 (2) 2.1算法原理 (2) 2.2计算过程 (2) 2.3改进的算法（Dijkstra-like）分析 (5) 三、源码分析 (5) 四、接口调用 (6) 一、算法概述 Dijkstra（迪杰斯特拉）算法是典型的单源最短路径计算算法，用于解决源点到所有结点最短路径计算的问题，它采用了分治和贪心（动态规划的特殊形式）的思想搜索全局最优解。 本系统采用了主流、开源的JA V A图论库——Jgrapht来解决源点到终点间所有可能路径输出的问题，它的核心计算引擎采用了一种Dijkstra-like算法，由经典的Dijkstra（迪杰斯特拉）算法演化和改进而来。 二、算法原理及计算 2.1算法原理 Dijkstra算法思想为：设(,) = 是带权有向图，V代表图中顶点集合，E G V E 代表图中含权重的边集合。将全部顶点集合V分成两组，第一组为已求出最短路径的顶点集合，用S表示（初始时S中只有一个源点，以后每求得一条最短路径，就将该路径的终点加入到集合S中）；第二组为其余待确定最短路径的顶点集合，用U表示。按最短路径长度的递增次序依次把U集合的顶点逐个加入到S集合中，约束条件是保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。算法的终止条件是集合U为空集，即集合U的顶点全部加入到集合S中。 2.2计算过程 以图1为例讨论Dijkstra算法的计算过程，即计算某源点到网络上其余各结点的最短路径，设源点为①，逐步搜索，每次找出一个结点到源点①的最短路径，直至完成所有结点的计算。 Dijkstra 算法应用举例 20061002516 张昕 123062 16 某城市部分街道如下图所示 求1v 到其他点的最短距离。 源程序如下 #include int nvertices; int nedges; } graph; initialize_graph(graph* g) { int i; g -> nvertices = 0; g -> nedges = 0; for (i=1; i<=MAXV; i++) g->degree[i] = 0; } insert_edge(graph* g,int x,int y,int directed,int w) { if (g->degree[x] > MAXDEGREE) printf("Warning: insertion(%d,%d) exceeds degree bound\n",x,y); g->edges[x][g->degree[x]].v = y; g->edges[x][g->degree[x]].weight = w; g->degree[x] ++; if (directed == FALSE) insert_edge(g,y,x,TRUE,w); else g->nedges ++; } read_graph(graph* g,int directed) { int i; int m; int x,y,w; initialize_graph(g); char* m_n = "8 12"; Dijkstra’s算法设计与分析实验 1．Dijkstra’s算法:的实现。 注：本算法来自教材（英文版），在此就省略了，只给出具体实现的程序代码，采用Microsoft Visual C++ 6.0实现，并且图的存储结构为邻接表。 ①本项目的组成结构如图所示 ②各对应模块的功能如下： asjacent(VNOde v,int a)：判断二接点是否相邻。 belong(int A[],int n,int p): 判断一个元素是否在指定数组中。 dijkstra(Vnode G[],int n):求最短路径问题的函数。 length(Vnode v,int a): 找出二相邻接点的长度。 main():主函数。 min(int r[],int Y[],int n):找出最小的元素的下标. shanchu(int A[],int sum,int p):删除数组中值为p的元素(覆盖). ③对应完整程序： #include 基本的dijkstra算法是求单源点到其余各点的最短路径，下面的dijkstra可以返回两个顶点之间的最短路径。返回数组里储存的是从起始顶点到结束顶点的最短路径经过的点的顺序。 package DijkstraJingxi; public class Dijkstra{ public void dijkstra(int n, int v, int dist[], int prev[],int[][] c){ int maxint = Integer.MAX_VALUE; // 表示最大整数上限 boolean[] s = new boolean[n]; //记录该点是否被访问过 for(int i = 0; i < n; i++){ dist[i] = c[v][i]; //目的地点初始化 s[i] = false; //记录第i个点是否被访问过，初始化为false； if(dist[i] == maxint){ prev[i] = 0; } else{ prev[i] = v; //起始点 } } dist[v] = 0; s[v] = true; //被访问过 for(int i = 0; i < n+1; i++){ int temp = maxint; int u = v; for(int j = 0; j < n; j++){ if((!s[j]) && (dist[j] < temp)){ u = j; //得到最短路径的终点 temp = dist[j]; } } s[u] = true; for(int j = 0; j < n; j++){ if((!s[j]) && (c[u][j] < maxint)){ int newdist = dist[u] + c[u][j]; if (newdist < dist[j]){ dist[j] = newdist; //新的最短路径 prev[j] = u; //最短路径的上一个点 } } } } } public int[] shortestPath(Graphm G, int v1, int v2){ Dijkstra算法的流程图 需求和规格说明： Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列，但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身 就不是难题了。实现注释： 想要实现的功能： Dijkstra算法是用来求任意两个顶点之间的最短路径。在该实验中，我们用邻接矩阵来存储图。在该程序中设置一个二维数组来存储任意两个顶点之间的边的权值。用户可以将任意一个图的信息通过键盘输入，让后在输入要查找的两个顶点，程序可以自动求出这两个顶点之间的最短路径。 已经实现的功能： 在该实验中，我们用邻接矩阵来存储图。在该程序中设置一个全局变量的二维数组，用它来存储任意两个顶点之间的边的权值。然后通过最短路径的计算，输入从任意两个顶点之间的最短路径的大小。 用户手册： 对于改程序，不需要客户进行什么复杂的输入，关键是用来存放图的任意两个顶点之间的边的权值的二维数组的初始化，即将要通过Dijkstra算法求最短路径的图各条边的权值放入二维数组中。这样程序就可以自动的计算出任意两个顶点之间的最短路径并且进行输出。设计思想： s为源，w[u，v] 为点u 和v 之间的边的长度，结果保存在dist[] 初始化：源的距离dist[s]设为0，其他的点距离设为无穷大，同时把所有的点状态设为没有扩展过。 循环n-1次： 1. 在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。 2. 对于每个与u相邻的点v，如果dist[u] + w[u，v] < dist[v]，那么把dist[v]更新成更短的距离dist[u] + w[u，v]。此时到点v的最短路径上，前一个节点即为u。 结束：此时对于任意的u，dist[u]就是s到u的距离。 效果展示： 开头输入的是点的序列号（表示第几个点），显示的是最短路径的走法（同样以点的序列号显示，表示途径的第几个点）。 %编写m文件 function [distance,path]=dijkstra(A,s,e) % [DISTANCE,PATH]=DIJKSTRA(A,S,E) % returns the distance and path between the start node and the end node. % % A: adjcent matrix % s: start node % e: end node % initialize n=size(A,1); % node number D=A(s,:); % distance vector path=[]; % path vector visit=ones(1,n); % node visibility visit(s)=0; % source node is unvisible parent=zeros(1,n); % parent node % the shortest distance for i=1:n-1 % BlueSet has n-1 nodes temp=zeros(1,n); count=0; for j=1:n if visit(j) temp=[temp(1:count) D(j)]; else temp=[temp(1:count) inf]; end count=count+1; end [value,index]=min(temp); j=index; visit(j)=0; for k=1:n if D(k)>D(j)+A(j,k) D(k)=D(j)+A(j,k); parent(k)=j; end #include "stdafx.h" #include "stdio.h" #include for(i=1;i D i j k s t r a算法详细讲 解 IMB standardization office【IMB 5AB- IMBK 08- IMB 2C】 最短路径之D i j k s t r a算法详细讲解? １?最短路径算法 在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括： （１）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 （２）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 （３）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 （４）全局最短路径问题：求图中所有的最短路径。 用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。 本文主要研究Dijkstra算法的单源算法。 ２?Dijkstra算法 Dijkstra算法 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 Dijkstra算法思想 Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径,就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v 到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 Dijkstra算法具体步骤 （1）初始时，S只包含源点，即S＝，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。最短路径的Dijkstra算法及Matlab程序
Dijkstra算法
dijkstra算法
Dijkstra最短路径算法
DIJKSTRA算法详细讲解
Dijkstra算法
Dijkstra算法
Dijkstra 算法（狄克斯特拉算法） 算法（狄克斯特拉算法）
目录
[隐藏]
? ? ? ? ? o ?
1 2 3 4 5
Dijkstra 算法概述 算法描述 虚拟码 时间复杂度 Dijkstra 算法案例分析 5.1 案例一:基于 Dijkstra 算法在物流配送中的应用[1] 6 参考文献
[编辑]
Dijkstra 算法概述
Dijkstra 算法 算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于 1959 年提出的，因此 又叫狄克斯特拉算法。 是从一个顶点到其余各顶点的最短路径算法， 解决的是有向图中最短 路径问题。 其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权 都为正时， 由于不会存在一个距离更短的没扩展过的点， 所以这个点的距离永远不会再被改 变， 因而保证了算法的正确性。 不过根据这个原理， Dijkstra 求最短路的图不能有负权边， 用 因为扩展到负权边的时候会产生更短的距离， 有可能就破坏了已经更新的点距离不会改变的 性质。 举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。 Dijkstra 算法可以用来找到两个城市之间的最短路径。 Dijkstra 算法的输入包含了一个有权重的有向图 G，以及 G 中的一个来源顶点 S。 我 们以 V 表示 G 中所有顶点的集合。 每一个图中的边，都是两个顶点所形成的有序元素对。 (u,v)表示从顶点 u 到 v 有路径相连。 我们以 E 所有边的集合，而边的权重则由权重函数 w: E → [0, ∞]定义。 因此，w(u,v)就是从顶点 u 到顶点 v 的非负花费值(cost)。 边的花费 可以想像成两个顶点之间的距离。 任两点间路径的花费值， 就是该路径上所有边的花费值总 和。已知有 V 中有顶点 s 及 t， Dijkstra 算法可以找到 s 到 t 的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。Dijkstra算法C代码
Dijkstra算法详细讲解
Dijkstra算法原理详细讲解
Dijkstra算法详细讲解资料整理
Dijkstra算法描述
Dijkstra算法应用举例
Dijkstra算法实现与分析
基本的dijkstra算法
Dijkstra算法的流程图
暴强Dijkstra算法求任意两点间最短路径
dijkstra算法的C语言实现
Dijkstra算法详细讲解
相关主题
文本预览