❶ Floyd算法除了能求出最短距离值外,还能求出最短路径吗它和Dijstra算法有什么区别
Floyd算法可以求出最短路径 但要求除了距离矩阵之外 还要保存一个结果矩阵 用结果矩阵还原出最短路
Floyd算法跟Dijstra算法最主要的区别在于 Floyd算法可以给出所有顶点间的最短路径 而Dijstra只能给出从一个特定顶点到其他顶点的最短路径 同时 Floyd算法的复杂度为O(V^3) 而Dijstra的复杂度是 O(E+VlogV) (用斐波那契堆)
❷ 最短路径 | 深入浅出Dijkstra算法（一）
上次我们介绍了神奇的只有 五行的 Floyd-Warshall 最短路算法 ，它可以方便的求得 任意两点的最短路径， 这称为 “多源最短路”。
这次来介绍 指定一个点（源点）到其余各个顶点的最短路径， 也叫做 “单源最短路径”。 例如求下图中的 1 号顶点到 2、3、4、5、6 号顶点的最短路径。
与 Floyd-Warshall 算法一样，这里仍然 使用二维数组 e 来存储顶点之间边的关系， 初始值如下。
我们还需要用 一个一维数组 dis 来存储 1 号顶点到其余各个顶点的初始路程， 我们可以称 dis 数组为 “距离表”， 如下。
我们将此时 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，现在来总结一下刚才的算法。 Dijkstra算法的基本思想是：每次找到离源点（上面例子的源点就是 1 号顶点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。
基本步骤如下：
在 博客 中看到两个比较有趣的问题，也是在学习Dijkstra时，可能会有疑问的问题。
当我们看到上面这个图的时候，凭借多年对平面几何的学习，会发现在“三角形ABC”中，满足不了 构成三角形的条件(任意两边之和大于第三边)。 纳尼，那为什么图中能那样子画？
还是“三角形ABC”，以A为起点，B为终点，如果按照平面几何的知识， “两点之间线段最短”， 那么，A到B的最短距离就应该是6(线段AB)，但是，实际上A到B的最短距离却是3+2=5。这又怎么解释？
其实，之所以会有上面的疑问，是因为 对边的权值和边的长度这两个概念的混淆， 。之所以这样画，也只是为了方便理解（每个人写草稿的方式不同，你完全可以用别的方式表示，只要便于你理解即可）。
PS：数组实现邻接表可能较难理解，可以看一下 这里
参考资料：
Dijkstra算法是一种基于贪心策略的算法。每次新扩展一个路程最短的点，更新与其相邻的点的路程。当所有边权都为正时，由于不会存在一个路程更短的没扩展过的点，所以这个点的路程永远不会再被改变，因而保证了算法的正确性。
根据这个原理， 用Dijkstra算法求最短路径的图不能有负权边， 因为扩展到负权边的时候会产生更短的路径，有可能破坏了已经更新的点路径不会发生改变的性质。
那么，有没有可以求带负权边的指定顶点到其余各个顶点的最短路径算法（即“单源最短路径”问题）呢？答案是有的， Bellman-Ford算法 就是一种。（我们已经知道了 Floyd-Warshall 可以解决“多源最短路”问题，也要求图的边权均为正）
通过 邻接矩阵 的Dijkstra时间复杂度是 。其中每次找到离 1 号顶点最近的顶点的时间复杂度是 O(N)，这里我们可以用 优先队列（堆） 来优化，使得这一部分的时间复杂度降低到 。这个我们将在后面讨论。
❸ 求邻接矩阵任意两点间的最短距离。matlab。程序在下面有没有哪位大神能给解释一下后边的是什么意思
根据lz要求，最合适的是floyd算法
下面就是根据这个算法写的代码，lz可以自己改成函数
D=[0 1 0 1 0 0
1 0 1 0 0 0
0 1 0 1 1 1
1 0 1 0 1 0
0 0 1 1 0 1
0 0 1 0 1 0];
n=length(D);
for k=1:n
for i=1:n
for j=1:n
if 0<D(i,k) & 0<D(k,j)
if D(i,j)==0 & i~=j
D(i,j)=D(i,k)+D(k,j);
else
D(i,j)=min(D(i,j),D(i,k)+D(k,j));
end
end
end
end
end
答案就储存在D矩阵当中，这里
D =
0 1 2 1 2 3
1 0 1 2 2 2
2 1 0 1 1 1
1 2 1 0 1 2
2 2 1 1 0 1
3 2 1 2 1 0
算法为O(n3)的，256^3=2^24 大概等于1600万
效率上完全能够忍受。
❹ 矩阵乘法求最短路径
们把求A →E 的最短路分解为四个阶段A →B →C→D →E 来求解.每一个阶段可以用一个矩阵来表示,这个矩阵称为权矩阵.相邻阶段的路径可以用权矩阵的乘积来表示.但这里的矩阵乘法和普通矩阵乘积运算的区别是:普通矩阵乘积其对应元素是相应元素乘积的代数和,这里把元素相乘改为相加,元素的代数和改为取小运算,如果不同层节点间没有连接,则视它们之间的距离为无穷大. 如果是求极大,改为取大运算,此时如果不同层节点间没有连接,则视它们的距离为0.
如下：
由A地到B地的距离可表示为：A[2 5 8]
由B地到C地的权矩阵可表示为
[3,6,5；7,10,8；4,9,6]
因此由A到C的权矩阵为[2,5,8][3,6,5；7,10,8；4,9,6]＝[5,8,7]
因此由A到D的权矩阵为[5,8,7)][7,5；3,4；5,2]＝[11 ,9]
由A→E的权矩阵为：[11 ,9][4,2)]=[15,11]
因此从家里到学校的最短距离为11百米,最近的路径为从A地出发经过B1地C1地D2地到达E地.
下面我们给出基于“矩阵乘法”求解最短路的算法:
第一阶段:计算出图中从起始点到终点最短路的长度.
step1 划分出该网络图中的层次关系(网络划分为N 层,起点为第一层,终点为第N 层) ;
step2 依次给出从第i 层到第i + 1 层的权矩阵( i= 1 ,2 , …, N21) ; (若第i 层有m 个顶点;第i + 1 层有n
个顶点, 则从第i 层到第i + 1 层的权矩阵为m *n
阶) .
step3 按照我们定义的矩阵乘法计算出最短路的
数值.
第二阶段:寻找最短路所经过的中间点.
(利用第一阶段中step2 的数据) 计算出从第i 层到
终点的最短路, 对比与i21 层到终点的最短路, 从而确
定出第i 层上最短路所经过的顶点( i = 2 , …, N21) .
❺ matlab实现floyd算法 已知距离矩阵和权值矩阵 求最短路径
希望可以帮到你。
function [D,path]=floyd(a)
n=size(a,1);
D=a;
path=zeros(n,n);
for i=1:n
for j=1:n
if D(i,j)~=inf
path(i,j)=j;
end
end
end
for k=1:n
for i=1:n
for j=1:n
if D(i,k)+D(k,j)<D(i,j)
D(i,j)=D(i,k)+D(k,j);
path(i,j)=path(i,k)
end
end
end
end
function [L,R]=router(D,path,s,t)
L=zeros(0,0);
R=s;
while 1
if s==t
L=fliplr(L);
L=[0,L];
return
end
L=[L,D(s,t)];
R=[R,path(s,t)];
s=path(s,t);
end
❻ 物流定量分析方法中的矩阵乘法和除法怎样计算的
一些符号贴不上来，蛋卷给你矩阵乘法PPT下载地址吧,除法可以换算成乘法来算的，给你2个PPT下载地址，你好好复习一下，呵呵。【PPT】矩阵乘法 地址1: http://jw1.nwnu.e.cn/jpkc/jwc/2004jpkc/gdds/jxkj/5.ppt2次型矩阵乘法 地址2： http://course.cug.e.cn/cugFourth/gddsh/page/jxzy/05.ppt希望蛋卷的回答可以帮上你。
❼ 谁告诉我物流中的去线破圈法是怎样的
配送路线三－破圈法下图为是一张高速公路网络示意图，其中A是起点，J是终点，B、C、D、E、G、H、I是网络上的节点，节点与节点之间以线路连接，线路上的数字表明了两个节点之间的距离。求从起点A到终点J之间的最短运输路线。解：用破圈法求解得最短路线为：A－B－E－I－J。最短运输距离为90+90+84+126=390公里。图中虚线表示破圈过程，即去掉的边情形。粗实线表示最短路线。图片参考地址： http://www.sina88.com/com/xdfpx/down/1100578578.doc 匈牙利法运算法则： １先将欲指派工作之人员与将分派之工作或机器设备等，可能发生之成本（或可能产生之绩效）列成相对应之方阵。 ２将方阵每列各数值减以各该列中之最小值。 ３再将每行中各数值减以各该行中之最小值。 ４尽可能以最少直线，纵线或横线，划去方阵中全部 若所划直线数目与拟分派的工作项目或拟指派的人员数目，即方阵的行数或列数相等时，即已获得最佳指派；否则，继续进行下一步骤。 ５寻求方阵中未被划线的最小数值，将所有未被划线的各数减此最小数值，并将有直线相交的数字，加以此最小数值，其余划线的数值不变，然后在回到第四步骤求解。 例：某师师部有后勤官、训练官、人事官、营务官四项职缺待分配，人事业管单位签拟甲、乙、丙、丁四位军官候选，虽然他们四人都可担当这四项职务中的任意一项，但由于个人经历、学历、专长、性格特点等情况有差别，每个人担任不同职务时效率都不一样，人事科长于是用匈牙利法给每个人每项职务打分数如表所示 贵官为人事科长，应该如何分配这四个人工作？ 解： １将矩阵的每列减去该列最小元素，得表 ２将矩阵的每行减去该行最小元素，得表 ３用三条直线可划去所有含有 的行或列，需继续叠代，得表 ４用四条直线可划去所有含 之行或列，即得最适解，得表 ５进行分派： 即甲─人事官；乙─营务官；丙─后勤官；丁─训练官；从上述四位军官分配的职务情况来看，甲、乙、丁是最大限度发挥专长，虽然丙没有发挥其专长，但整体效益却是最高的，其总分为４０＋３６＋３５＋４３＝１５４。
❽ 如何由邻接矩阵求出距离矩阵
最简单是用Floyd法,即是用动态规划做道路松弛. 先将道路邻接矩阵填入d(i,j).
过程:枚举i,j,k:d(i,j)=min{d(i,k)+d(k,j)}
最后得到的d(i,j)就是距离.
❾ 数学建模 求最短距离 最好能用多种方法
用matlab解
%求A到E的最短距离
AB=[2 4 3];
BC=[7 4 6;3 2 4;4 1 5];
CD=[1 4;6 3;3 3];
DE=[3;4];
l=zeros(1,100)+1000;
n=1;
for a=1:3
L=AB(1,a);
for b=1:3
L=L+BC(a,b);
for c=1:2
L=L+CD(b,c)+DE(c,1);
l(1,n)=L;
n=n+1;
end
end
end
minL=min(l)
运行程序得到minL=11
数学模型
（Mathematical Model）是一种模拟，是用数学符号、数学式子、程序、图形等对实际课题本质属性的抽象而又简洁的刻画，它或能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略。
数学模型一般并非现实问题的直接翻版，它的建立常常既需要人们对现实问题深入细微的观察和分析，又需要人们灵活巧妙地利用各种数学知识。
❿ 求教：蚁群算法选择最短路径问题
这个例子其实是当初数模比赛时用来完成碎片拼接的，但其所用到原理还是求解最短路径的原理。但这里的最短路径和数据结构中最短路径有一定的区别。在数据结构中，对于最短路径的求解常用的一般有Dijkstra算法与Floyd算法，但对于要求出一条经过所有的点的并且要求路径最短，这些算法还是有一定的局限性的。而蚁群算法则很好地满足了这些条件。话说回来，很想吐槽一下网络流传的一些蚁群算法的例子，当初学习这个时候，身边也没有相关的书籍，只好到网上找例子。网上关于这个算法源代码的常见的有2个版本，都是出自博客，但是在例子都代码是不完整的，缺失了一部分，但就是这样的例子，居然流传甚广，我很好奇那些转载这些源码的人是否真的有去学习过这些，去调试过。当然，我下面的例子也是无法直接编译通过的，因为涉及到图像读取处理等方面的东西，所以就只贴算法代码部分。但是对于这个问题蚁群算法有一个比较大的缺点，就是收敛很慢，不过对于数量小的路径，效果还是很好的。function bestqueue =aco1(nt,nc_max,m ,st, sd ,Alpha ,Beta ,Rho ,Q,gethead,getend)%参数解释：%nt 路径所经过的点的个数；%nc_max 迭代的次数；%m 蚂蚁的个数；%st 起点序号；%sd 终点序号；%Alpha 信息素系数；�ta 启发因子系数；%Rho 蒸发系数；% Q 信息量；%gethead getend 是用来求距离矩阵的，可根据实际情况修改
% nt = 209;%碎片个数full = zeros(nt,nt);tic;%初始化距离矩阵for i =1:nt for t = 1:nt if i ~= t full(i,t) = sum(abs(getend(:,i) - gethead(:,t))); else full(i,t) = inf; end endend% a =full(156,187)eta = 1./full;%启发因子，取距离的倒数% eta% e = eta(4,2)tau = ones(nt,nt);%信息素矩阵% tabu = zeros(nt,nt);%禁忌矩阵，取蚂蚁数量和碎片数量一致，以减少迭代次数nc =1;%初始化迭代次数;rbest=zeros(nc_max,nt);%各代最佳路线rbest(:,1) = (linspace(st,st,nc_max))';rbest(:,nt) =(linspace(sd,sd,nc_max))'; lbest=zeros(nc_max,1);%各代最佳路线的长度pathlen = 0;%临时记录每代最佳路线长度stime = 1;%记录代数进度for i = 1:nc_max % 代数循环 delta_tau=zeros(nt,nt);%初始化改变量 stime for t = 1:m % 对蚂蚁群体的循环， tabu=zeros(1,nt);%禁忌向量，标记已访问的碎片，初试值设为0，访问之后则变为1; viseted = zeros(1,nt);%记录已访问的元素的位置 tabu(st) = 1;%st为起点，在此表示为碎片矩阵的编号，因为已经将蚁群放在起点，故也应将禁忌向量和位置向量的状态进行修改 tabu(sd) =1;%同上 visited(nt) = sd ;%同上； visited(1) = st;%同上； ht = 0; for r = 2:nt-1 %记录了还没访问的图片编号 vp = 1;%visited指示量 pp = [];%置空的概率向量 jc = 0; %获取尚未访问的位置的向量。 wv = zeros( nt -2 - ht ); for k =1 : nt if tabu(k) == 0 jc = jc +1; wv(jc) = k; end end% a =(tau(visited(end),ju(3))^Alpha)*(eta(visited(end),ju(3))^Beta)% visited(end) %计算选择的概率 for k=1:length(wv) pp(k)=(tau(visited(vp),wv(k))^Alpha)*(eta(visited(vp),wv(k))^Beta);%下一张碎片的选择概率计算，p =（信息素^信息素系数）*（启发因子^启发因子系数） end pp=pp./(sum(pp));%归一化 pcum =cumsum(pp); psl = find(pcum >= rand);%轮盘赌法 to_visit= wv(psl(1)) ;%完成选点 tabu(to_visit) =1; visited(r) = to_visit; ht =ht +1;%已访问碎片个数变化 vp =vp+1; end %路径变化信息 %对单个蚂蚁的路径进行统计 sum1 =0; for pr = 1:nt -1 x = visited(pr); y = visited(pr+1) ; sum1 =sum1 + full(x,y); end% vcell{t} =visited;%元胞记录每个蚂蚁的路径，即碎片顺序;% msum(t) = sum1; %信息素变化； for ww=1:(nt-1) delta_tau(visited(ww),visited(ww+1))=delta_tau(visited(ww),visited(ww+1)) + Q/sum1; end% delta_tau(visited(end),visited(1))=delta_tau(visited(end),visited(1))+Q/(sum1/100);% if t == m & i == nc_max % bestqueue = visited% end if t == m bestqueue = visited end end tau=(1-Rho).*tau+delta_tau; %完成信息素的更新，找出现有的最新的最佳路径,即信息素最多的路径； stime =stime +1;end toc;