最短路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
1 2 0 0 0 0 0 0 0 0 0
1 2 3 0 0 0 0 0 0 0 0
1 2 3 4 0 0 0 0 0 0 0
1 2 3 10 9 7 6 11 5 0 0
1 2 3 10 9 7 6 0 0 0 0
1 2 3 10 9 7 0 0 0 0 0
1 8 0 0 0 0 0 0 0 0 0
1 2 3 10 9 0 0 0 0 0 0
1 2 3 10 0 0 0 0 0 0 0
1 2 3 10 9 7 6 11 0 0 0 此外，改变程序中变量s和t的取值，可以得到其他顶点之间的最短路径。
两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。 以各城镇为图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||- 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 function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta ,Rho,Q) %%===================================================== ==================== %% ACATSP.m %% Ant Colony Algorithm for Traveling Salesman Problem %% ChengAihua,PLA Information Engineering University,ZhengZhou,China %% Email:aihuacheng@https://www.doczj.com/doc/524732167.html, %% All rights reserved %%------------------------------------------------------------------------- %% 主要符号说明 %% C n个城市的坐标，n×4的矩阵 %% NC_max 最大迭代次数 %% m 蚂蚁个数 %% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 信息素增加强度系数 %% R_best 各代最佳路线 %% L_best 各代最佳路线的长度 %%===================================================== ==================== %%第一步：变量初始化 n=size(C,1);%n表示问题的规模（城市个数） D=zeros(n,n);%D表示完全图的赋权邻接矩阵 for i=1:n for j=1:n if i~=j D(i,j)=max( ((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5,min(abs(C(i,3)-C(j,3)),144- abs(C(i,3)-C(j,3))) );%计算城市间距离 else D(i,j)=eps; end D(j,i)=D(i,j); end end Eta=1./D;%Eta为启发因子，这里设为距离的倒数 Tau=ones(n,n);%Tau为信息素矩阵 Tabu=zeros(m,n);%存储并记录路径的生成 NC=1;%迭代计数器 R_best=zeros(NC_max,n);%各代最佳路线 学号： 课程设计 题目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) 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 先新建一个主程序M文件ACATSP.m 代码如下: function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q) %%================================================== ======================= %% 主要符号说明 %% C n个城市的坐标，n×2的矩阵 %% NC_max 蚁群算法MATLAB程序最大迭代次数 %% m 蚂蚁个数 %% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 表示蚁群算法MATLAB程序信息素增加强度系数 %% R_best 各代最佳路线 %% L_best 各代最佳路线的长度 %%================================================== ======================= %% 蚁群算法MATLAB程序第一步：变量初始化 n=size(C,1);%n表示问题的规模（城市个数） D=zeros(n,n);%D表示完全图的赋权邻接矩阵 for i=1:n for j=1:n if i~=j D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5; else D(i,j)=eps; % i = j 时不计算，应该为0，但后面的启发因子要取倒数，用eps（浮点相对精度）表示 end D(j,i)=D(i,j); %对称矩阵 end end Eta=1./D; %Eta为启发因子，这里设为距离的倒数 Tau=ones(n,n); %Tau为信息素矩阵 Tabu=zeros(m,n); %存储并记录路径的生成 最短路径—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有边， 则 蚁群算法的matlab源码，同时请指出为何不能优化到已知的最好解 % % % the procedure of ant colony algorithm for VRP % % % % % % % % % % % % %initialize the parameters of ant colony algorithms load data.txt; d=data(:,2:3); g=data(:,4); m=31; % 蚂蚁数 alpha=1; belta=4;% 决定tao和miu重要性的参数 lmda=0; rou=0.9; %衰减系数 q0=0.95; % 概率 tao0=1/(31*841.04);%初始信息素 Q=1;% 蚂蚁循环一周所释放的信息素 defined_phrm=15.0; % initial pheromone level value QV=100; % 车辆容量 vehicle_best=round(sum(g)/QV)+1; %所完成任务所需的最少车数V=40; % 计算两点的距离 for i=1:32; for j=1:32; dist(i,j)=sqrt((d(i,1)-d(j,1))^2+(d(i,2)-d(j,2))^2); end; end; %给tao miu赋初值 for i=1:32; for j=1:32; if i~=j; %s(i,j)=dist(i,1)+dist(1,j)-dist(i,j); tao(i,j)=defined_phrm; miu(i,j)=1/dist(i,j); end; end; end; for k=1:32; for k=1:32; deltao(i,j)=0; end; end; best_cost=10000; for n_gen=1:50; print_head(n_gen); for i=1:m; %best_solution=[]; print_head2(i); 图论实验三个案例 单源最短路径问题 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) function [y,val]=QACStic load att48 att48; MAXIT=300; % 最大循环次数 NC=48; % 城市个数 tao=ones(48,48);% 初始时刻各边上的信息最为1 rho=0.2; % 挥发系数 alpha=1; beta=2; Q=100; mant=20; % 蚂蚁数量 iter=0; % 记录迭代次数 for i=1:NC % 计算各城市间的距离 for j=1:NC distance(i,j)=sqrt((att48(i,2)-att48(j,2))^2+(att48(i,3)-att48(j,3))^2); end end bestroute=zeros(1,48); % 用来记录最优路径 routelength=inf; % 用来记录当前找到的最优路径长度 % for i=1:mant % 确定各蚂蚁初始的位置 % end for ite=1:MAXIT for ka=1:mant %考查第K只蚂蚁 deltatao=zeros(48,48); % 第K只蚂蚁移动前各边上的信息增量为零 [routek,lengthk]=travel(distance,tao,alpha,beta); if lengthk 蚁群算法matlab精讲及仿真 4.1基本蚁群算法 4.1.1基本蚁群算法的原理 蚁群算法是上世纪90年代意大利学者M.Dorigo,v.Maneizz。等人提出来的,在越来越多的领域里得到广泛应用。蚁群算法，是一种模拟生物活动的智能算法，蚁群算法的运作机理来源于现实世界中蚂蚁的真实行为，该算法是由Marco Dorigo 首先提出并进行相关研究的，蚂蚁这种小生物，个体能力非常有限，但实际的活动中却可以搬动自己大几十倍的物体，其有序的合作能力可以与人类的集体完成浩大的工程非常相似，它们之前可以进行信息的交流，各自负责自己的任务，整个运作过程统一有序，在一只蚂蚁找食物的过程中，在自己走过的足迹上洒下某种物质，以传达信息给伙伴，吸引同伴向自己走过的路径上靠拢，当有一只蚂蚁找到食物后，它还可以沿着自己走过的路径返回，这样一来找到食物的蚂蚁走过的路径上信息传递物质的量就比较大，更多的蚂蚁就可能以更大的机率来选择这条路径，越来越多的蚂蚁都集中在这条路径上，蚂蚁就会成群结队在蚁窝与食物间的路径上工作。当然，信息传递物质会随着时间的推移而消失掉一部分，留下一部分，其含量是处于动态变化之中，起初，在没有蚂蚁找到食物的时候，其实所有从蚁窝出发的蚂蚁是保持一种随机的运动状态而进行食物搜索的，因此，这时，各蚂蚁间信息传递物质的参考其实是没有价值的，当有一只蚂蚁找到食物后，该蚂蚁一般就会向着出发地返回，这样，该蚂蚁来回一趟在自己的路径上留下的信息传递物质就相对较多，蚂蚁向着信息传递物质比较高的路径上运动，更多的蚂蚁就会选择找到食物的路径，而蚂蚁有时不一定向着信 息传递物质量高的路径走，可能搜索其它的路径。这样如果搜索到更短的路径后，蚂蚁又会往更短的路径上靠拢，最终多数蚂蚁在最短路径上工作。【基于蚁群算法和遗传算法的机器人路径规划研究】 该算法的特点： (1)自我组织能力，蚂蚁不需要知道整体环境信息，只需要得到自己周围的信息，并且通过信息传递物质来作用于周围的环境，根据其他蚂蚁的信息素来判断自己的路径。 (2)正反馈机制，蚂蚁在运动的过程中，收到其他蚂蚁的信息素影响，对于某路径上信息素越强的路径，其转向该路径的概率就越大，从而更容易使得蚁群寻找到最短的避障路径。 (3)易于与其他算法结合，现实中蚂蚁的工作过程简单，单位蚂蚁的任务也比较单一，因而蚁群算法的规则也比较简单，稳定性好，易于和其他算法结合使得避障路径规划效果更好。 (4)具有并行搜索能力探索过程彼此独立又相互影响，具备并行搜索能力，这样既可以保持解的多样性，又能够加速最优解的发现。 4.1.2 基本蚁群算法的生物仿真模型 a为蚂蚁所在洞穴,food为食物所在区,假设abde为一条路径,eadf为另外一条路径,蚂蚁走过后会留下信息素,5分钟后蚂蚁在两条路径上留下的信息素的量都为3,概率可以认为相同,而30分钟后baed路径上的信息素的量为60,明显大于eadf路径上的信息素的量。最终蚂蚁会完全选择abed这条最短路径,由此可见, function [y,val]=QACS tic load att48 att48; MAXIT=300; % 最大循环次数 NC=48; % 城市个数 tao=ones(48,48);% 初始时刻各边上的信息最为1 rho=0.2; % 挥发系数 alpha=1; beta=2; Q=100; mant=20; % 蚂蚁数量 iter=0; % 记录迭代次数 for i=1:NC % 计算各城市间的距离 for j=1:NC distance(i,j)=sqrt((att48(i,2)-att48(j,2))^2+(att48(i,3)-att48(j,3))^2); end end bestroute=zeros(1,48); % 用来记录最优路径 routelength=inf; % 用来记录当前找到的最优路径长度 % for i=1:mant % 确定各蚂蚁初始的位置 % end for ite=1:MAXIT for ka=1:mant %考查第K只蚂蚁 deltatao=zeros(48,48); % 第K只蚂蚁移动前各边上的信息增量为零 [routek,lengthk]=travel(distance,tao,alpha,beta); if lengthk 利用计算机语言编程实现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 算法流程如下图所示。 蚁群算法最短路径通用Matlab程序（附图） function [ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q) %% --------------------------------------------------------------- % ACASP.m % 蚁群算法动态寻路算法 % ChengAihua,PLA Information Engineering University,ZhengZhou,China % Email:aihuacheng@https://www.doczj.com/doc/524732167.html, % All rights reserved %% --------------------------------------------------------------- % 输入参数列表 % G 地形图为01矩阵，如果为1表示障碍物 % Tau 初始信息素矩阵（认为前面的觅食活动中有残留的信息素） % K 迭代次数（指蚂蚁出动多少波） % M 蚂蚁个数（每一波蚂蚁有多少个） % S 起始点（最短路径的起始点） % E 终止点（最短路径的目的点） % Alpha 表征信息素重要程度的参数 % Beta 表征启发式因子重要程度的参数 % Rho 信息素蒸发系数 % Q 信息素增加强度系数 % % 输出参数列表 % ROUTES 每一代的每一只蚂蚁的爬行路线 % PL 每一代的每一只蚂蚁的爬行路线长度 % Tau 输出动态修正过的信息素 %% --------------------变量初始化---------------------------------- %load D=G2D(G); N=size(D,1);%N表示问题的规模（象素个数） MM=size(G,1); a=1;%小方格象素的边长 Ex=a*(mod(E,MM)-0.5);%终止点横坐标 if Ex==-0.5 Ex=MM-0.5; end Ey=a*(MM+0.5-ceil(E/MM));%终止点纵坐标 Eta=zeros(1,N);%启发式信息，取为至目标点的直线距离的倒数 %下面构造启发式信息矩阵 for i=1:N if ix==-0.5 图论实验三个案例 单源最短路径问题 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算法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 蚁群算法最短路径通用Matlab程序 下面的程序是蚁群算法在最短路中的应用，稍加扩展即可应用于机器人路径规划 function [ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q) %% ---------------------------------------------------------------% ACASP.m % 蚁群算法动态寻路算法 % ChengAihua,PLA Information Engineering University,ZhengZhou,China % Email:aihuacheng@https://www.doczj.com/doc/524732167.html, % All rights reserved %% ---------------------------------------------------------------% 输入参数列表 % G 地形图为01矩阵，如果为1表示障碍物 % Tau 初始信息素矩阵（认为前面的觅食活动中有残留的信息素） % K 迭代次数（指蚂蚁出动多少波） % M 蚂蚁个数（每一波蚂蚁有多少个） % S 起始点（最短路径的起始点） % E 终止点（最短路径的目的点） % Alpha 表征信息素重要程度的参数 % Beta 表征启发式因子重要程度的参数 % Rho 信息素蒸发系数 % Q 信息素增加强度系数 % % 输出参数列表 % ROUTES 每一代的每一只蚂蚁的爬行路线 % PL 每一代的每一只蚂蚁的爬行路线长度 % Tau 输出动态修正过的信息素 %% --------------------变量初始化---------------------------------- %load D=G2D(G); N=size(D,1);%N表示问题的规模（象素个数） MM=size(G,1); a=1;%小方格象素的边长 Ex=a*(mod(E,MM)-0.5);%终止点横坐标 if Ex==-0.5 Ex=MM-0.5; end Ey=a*(MM+0.5-ceil(E/MM));%终止点纵坐标 Eta=zeros(1,N);%启发式信息，取为至目标点的直线距离的倒数 %下面构造启发式信息矩阵 for i=1:N if ix==-0.5 ix=MM-0.5;最短路dijkstra算法Matlab程序
蚁群算法TSP问题matlab源代码
dijkstra算法的matlab实现
dijkstra算法原理及MATLAB代码
蚁群算法matlab程序代码
Dijkstra算法
蚁群算法matlab
图论算法及matlab程序的三个案例
蚁群算法MATLAB代码
matlab蚁群算法精讲及仿真图
(完整版)蚁群算法matlab程序实例整理
利用MATLAB实现Dijkstra算法
蚁群算法最短路径通用Matlab程序(附图)
图论算法及matlab程序的三个案例
最短路dijkstra算法Matlab程序调用举例
蚁群算法最短路径matlab程序
相关主题
文本预览