* 给定一个带权有向图G = (V，E)，其中每条边的权是一个非负整数。* * 另外还给定V中的一个顶点，称为源。现在我们要计算从源到所有其* * 他各顶点的最短路长度。这里路径长度是路上各边权之和。这个问* * 题通常称为单源最短路径问题。*
***************************************************************/
#include
#define INFINITE 100
void main()
{
int j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout< d = new int[n]; s = new int[n]; p = new int[n]; w = new int*[n]; for(i = 0; i < n; i++) { w[i] = new int[n]; } for(i = 0; i < n; i++) for(j = 0; j < n; j++) cin>>w[i][j]; for(s[0] = 1,i = 1; i < n; i++) { s[i] = 0; d[i] = w[0][i]; if(d[i] < INFINITE) p[i]=0; else p[i]=-1; } for(i = 1; i < n; i++) { t = INFINITE; k = 1; for(j = 1; j < n; j++) if((!s[j]) && (d[j] < t)) { t = d[j]; k = j; } s[k]=1;//point k join the S for (j = 1; j < n; j++) if((!s[j]) && (d[j] > d[k] + w[k][j])) { d[j] = d[k] + w[k][j]; p[j] = k; } } cout<<"从源点到其它顶点的最短距离依次如下："; for(i=1;i cout< } /********* 顶点个数用n表示，这里给出的例子n=6 100 1 12 100 100 100 100 100 9 3 100 100 100 100 100 100 5 100 100 100 4 100 13 15 100 100 100 100 100 4 100 100 100 100 100 100 具体例子见电子工业出版社《算法设计技巧与分析》 两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。 以各城镇为图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发出后的下一跳结点（在算法中常称为“后继结点”）和距离。当然，像这样的路由表，在所有其他各结点中都有一个。但这就需要分别以这些结点为源结点，重新执行算法，然后才能找出以这个结点为根的最短路径树和相应的路由表。 function [c0,c,path0,path]=dijkstra(s,t,C,flag) % Use the Dijkstra's algorithm to find the shortest path from % s to t and can also find the shortest path between s and all % the other points. % Reference: Graph Theory with Applications by J. A. Bondy and % U. S. R. Murty. % Input -- s is the starting point and also is the point s. % -- t is the given terminal point and is the point t. % -- C \in R^{n \times n}is the cost matrix, where % C(i,j)>=0 is the cost from point i to point j. % If there is no direct connection between point i and % j, C(i,j)=inf. % -- flag: if flag=1, the function just reports the % shortest path between s and t; if flag~=1, the % function reports the shortest path between s and t, % and the shortest paths between s and other points. % Output -- c0 is the minimal cost from s to t. % -- path0 denotes the shortest path form s to t. % -- c \in R{1\times n} in which the element i is the % minimal cost from s to point i. % -- path \in R^{n \times n} in which the row i denotes % the shortest path from s to point i. % Copyright by MingHua Xu(徐明华), Changhzou University, 27 Jan. 2014. s=floor(s); t=floor(t); n=size(C,1); if s<1 || t < 1 || s > n || t > n error(' The starting point and the terminal point exceeds the valid range'); end if t==s disp('The starting point and the terminal point are the same points'); end label=ones(1,n)*inf; label(s)=0; S=[s]; Sbar=[1:s-1,s+1:n]; c0=0; path=zeros(n,n); path(:,1)=s; c=ones(1,n)*inf; parent=zeros(1,n); i=1; % number of points in point set S. while i 迪克斯特拉算法： 迪杰斯特拉算法(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中顶点对应的距离值 若存在 学号： 课程设计 题目Dijkstra算法的MATLAB实现 学院信息工程学院 专业通信工程 班级 姓名 指导教师 2012 年 1 月9 日 课程设计任务书 学生姓名：专业班级：通信 0901班 指导教师：工作单位：信息工程学院 题目: Dijkstra算法的MATLAB实现 初始条件： （1）MATLAB应用软件的基本知识以及基本操作技能 （2）高等数学、线性代数等基础数学中的运算知识 （3）数据结构里面关于Dijkstra算法的基本原理和思想 要求完成的主要任务: 必做题：采用MATLAB选用适当的函数或矩阵进行如下计算 （1）极限的计算、微分的计算、积分的计算、级数的计算、求解代数方程、求解常微分方程； （2）矩阵的最大值、最小值、均值、方差、转置、逆、行列式、特征值的计算、矩阵的相乘、右除、左除、幂运算； （3）多项式加减乘除运算、多项式求导、求根和求值运算、多项式的部分分式展开、多项式的拟合、插值运算。 选做题：Dijkstra算法的MATLAB实现 时间安排： 第一周，安排任务地点：鉴主17楼实验室 第1-17，周仿真设计地点：鉴主13楼计算机实验室 第18周，完成答辩，提交报告地点：鉴主17楼实验室 指导教师签名：年月日 系主任（或责任教师）签名：年月 目录 摘要................................................................................................................................. I Abstract ......................................................................................................................... II 1 MATLAB的基本运算 .. 0 1.1 基础微积分计算 0 1.1.1 极限的基本运算 0 1.1.2 微分的计算 0 1.1.3 积分的计算 (1) 1.1.4 级数的运算 (1) 1.1.5 求解代数微分方程 (1) 1.1.6 求解常微分方程 (2) 1.2 矩阵的基本运算 (2) 1.2.1 矩阵的最大最小值 (2) 1.2.2 矩阵的均值方差 (3) 1.2.3 矩阵的转置和逆 (3) 1.2.4 矩阵的行列式 (3) 1.2.5 矩阵特征值的计算 (3) 1.2.6 矩阵的相乘 (4) 1.2.7 矩阵的右除和左除 (4) 1.2.8 矩阵的幂运算 (4) 1.3 多项式的基本运算 (4) 1.3.1 多项式的四则运算 (4) 1.3.2 多项式的求导、求根、求值运算 (5) 1.3.3 多项式的部分分式展开 (5) 1.3.4 多项式的拟合 (5) 1.3.5 多项式的插值运算 (6) 2关于Dijkstra的问题描述 (6) 2.1问题的提出 (6) 2.2 Dijkstra算法的算法思想 (7) 2.3 Dijkstra算法的算法原理 (7) 3 Dijkstra算法的设计分析 (8) 3.1 Dijkstra算法部分的设计分析 (8) 3.2 程序主体的设计分析 (9) 4程序源代码与算法思想 (10) 4.1 文件isIn.m的源代码 (10) 4.2 文件default_dat.m的源代码 (11) 4.3 文件input_dat.m的源代码 (11) 4.4 文件menu.m的源代码 (11) 4.5 文件dijkstra.m的源代码 (13) 5 测试报告 (16) 6 心得体会 (17) 7 参考文献 (18) 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算法是寻找最短路径的一种搜索算法，由荷兰科学家提出。 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有边，则 过程如下： 在网上搜索一些版本的Matlab实现方法，感觉都有些毛病。经过修改，得到比较好的效果。[cpp]view plain copy 1.function [ distance path] = Dijk( W,st,e ) 2.%DIJK Summary of this function goes here 3.% W 权值矩阵 st 搜索的起点 e 搜索的终点 4.n=length(W);%节点数 5. D = W(st,:); 6.visit= ones(1:n); visit(st)=0; 7.parent = zeros(1,n);%记录每个节点的上一个节点 8. 9.path =[]; 10. 11.for i=1:n-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 算法 图论实验三个案例 单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=， 1{} i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果12 1n n v v v v -是从1v 到 n v 的最短路径，则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数+308)。 function re=Dijkstra(ma) #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]; 利用计算机语言编程实现D算法 一：实验目的 本实验课程主要目的是让学生够熟练掌握图论中的D算法。 二：实验方法 选择MATLAB语言编程实现D算法。 三：实验要求 1.输入必要参数，包括：节点个数、节点间路径长度、给定节点； 2.输出给定节点到其它各节点的最短路径、径长； 3.节点间路径长度用矩阵形式表示。 四：实验内容 无向图共有7个节点，如下图所示。 v1 45 7 计算机输入的节点间路径长度为7×7矩阵： 1234567 1 2 3 4 5 6 7 0123 106 2054 304 5407 6408 780?? ∞∞∞?? ∞∞∞∞?? ??∞∞∞??∞∞∞∞?? ??∞∞∞ ??∞∞∞ ????∞∞∞∞ ??v v v v v v v v v v v v v v 若 1 v为指定节点，则1v到其它各节点的最短路径及径长的计算机计算结果为： 提示：不相邻的两个节点间∞可以用相对较大的数代替（如输入100表示∞） 五：实验原理 1. D 算法原理 已知图G=(V,E)，将其节点集分为两组：置定节点集p G 和未置定节点集 p G G -。其中p G 内的所有置定节点，是指定点s v 到这些节点的路径为最短（即已完成最短路径的计算）的节点。而p G G -内的节点是未置定节点，即s v 到未置定节点距离是暂时的，随着算法的下一步将进行不断调整，使其成为最短径。在调整各未置定节点的最短径时，是将p G 中的节点作为转接点。具体地说，就是将p G 中的节点作为转接点，计算（s v ,j v ）的径长（j p v G G ∈-），若该次计算的径长小于上次的值，则更新径长，否则，径长不变。计算后取其中径长最短者，之后将j v 划归到p G 中。当（p G G -）最终成为空集，同时p G G =，即求得s v 到所有其他节点的最短路径。 j w 表示s v 与其他节点的距离。 在p G 中，i w 表示上一次划分到p G 中的节点i v 到s v 得最短路径。在 p G G -中，表示s v 到j v （j p v G G ∈-）仅经过p G 中的节点作为转接点所求得的该次的最短路径的长度。 如果s v 与j v 不直接相连，且无置定节点作为转接点，则令j w =∞。 2. D 算法实现流程 D 算法流程如下图所示。 图论实验三个案例 单源最短路径问题 1.1 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到 j v 的权 ij w =∞ 。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在1i v +，使1()min{()}i l v l v +=，v S ∈； ⑤ 1{}i S S v += ，1{}i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果121n n v v v v - 是从1v 到n v 的最短路径，则121n v v v - 也必然是从1v 到1n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元素表示顶点i v 到 j v 的权 ij w ，若i v 到 j v 无边，则 realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数(1.7977e+308)。 function re=Dijkstra(ma) 最短路径之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算法Matlab程序调用举例 2014/4/17 徐明华 设赋权图如下图所示 下述Matlab程序 % test dijkstra's algorithm % The test example is take from the following book % Graph Theory with Applications by J. A. Bondy and U. S. R. Murty. % Page 16. clc s=1; t=5; flag=1; W=ones(11,11)*inf; % for i=1:11 W(i,i)=0; end W(1,2)=2; W(2,1)=2; W(2,3)=1; W(3,2)=1; W(3,4)=2; W(4,3)=2; W(4,5)=9; W(5,4)=9; W(5,6)=4; W(6,5)=4; W(6,7)=1; W(7,6)=1; W(7,8)=9; W(8,7)=9; W(8,1)=1; W(1,8)=1; W(1,9)=8; W(9,1)=8; W(9,2)=6; W(2,9)=6; W(9,8)=7; W(8,9)=7; W(9,7)=2; W(7,9)=2; W(9,10)=1;W(10,9)=1; W(9,3)=5; W(3,9)=5; W(10,7)=4; W(7,10)=4; W(10,11)=6; W(11,10)=6; W(10,3)=3; W(3,10)=3; W(11,7)=3; W(7,11)=3; W(11,6)=1; W(6,11)=1; W(11,4)=7; W(4,11)=7; W(11,5)=2; W(5,11)=2; W(11,3)=9; W(3,11)=9; [c0,c,path0,path]=dijkstra(s,t,W,flag); c0 path0 调用matlab函数dijkstra(具体见本文库文档：最短路dijkstra算法Matlab程序), 可得到顶点v1 到顶点v5的最短路径path0及最短路径的长度c0如下： c0 = 13 path0 = 1 2 3 10 9 7 6 11 5 如果将上述程序中的语句 flag=1; 替换为 flag=2; 并将 [c0,c,path0,path]=dijkstra(s,t,C,flag); c0 path0 替换为 [c0,c,path0,path]=dijkstra(s,t,C,flag); c path 运行程序可得到顶点v1到图中其他各顶点的最短路径所成矩阵path和各最短路径的长度所成向量c，其中path的第i行表示v1到第i个顶点的最短路径，c(i) 为v1到第i个顶点的最短路径的长度。具体运算结果如下： c = 0 2 3 5 13 10 9 1 7 6 11 path = 1 0 0 0 0 0 0 0 0 0 0最短路径的Dijkstra算法及Matlab程序
Dijkstra算法
最短路dijkstra算法Matlab程序
dijkstra算法
dijkstra算法的matlab实现
Dijkstra最短路径算法
dijkstra算法原理及MATLAB代码
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 到任何其他顶点的最短路径。图论算法及matlab程序的三个案例
Dijkstra算法C代码
Dijkstra算法详细讲解
Dijkstra算法原理详细讲解
利用MATLAB实现Dijkstra算法
图论算法及matlab程序的三个案例
Dijkstra算法详细讲解资料整理
最短路dijkstra算法Matlab程序调用举例
相关主题
文本预览