关于公示网站建设的计划书,南通网站排名优化公司,做app网站的软件叫什么,关于网站建设实验报告文章目录
一、前言
二、最短路线
2.1 教程
2.1.1 sparse创建稀疏矩阵
2.1.2 有向图最短路径#xff08;1#xff09;
2.1.3 有向图最短路径#xff08;2#xff09;
2.1.4 无向图最短路径#xff08;1#xff09;
2.1.5无向图最短路径#xff08;2#xff09; …文章目录
一、前言
二、最短路线
2.1 教程
2.1.1 sparse创建稀疏矩阵
2.1.2 有向图最短路径1
2.1.3 有向图最短路径2
2.1.4 无向图最短路径1
2.1.5无向图最短路径2 一、前言
动态规划是求解某类问题的一种方法是考察问题的一种途径而不是一种特殊算法如线性规划是一种算法。因而它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则而必须对具体问题进行具体分析处理。因此在学习时除了要对基本概念和方法正确理解外应以丰富的想象力去建立模型用创造性的技巧去求解。
二、最短路线
2.1 教程
2.1.1 sparse创建稀疏矩阵
比如我们有这样的无向图 代码
%w(起点,终点)权重值clear all
clc
wzeros(4);
w(1,2)2;w(1,3)3;w(1,4)8;
w(2,3)6;w(2,4)6;
Gsparse(w)运行结果 或者这样创建稀疏矩阵
clear all
clc
%sparse([起点集合],[对应终点集合],[对应权重集合])
G sparse([1 1 1 2 2],[2 3 4 3 4],[2 3 8 6 6]);
ssparse(G)
运行结果 可以看出与上面一样 2.1.2 有向图最短路径1
使用函数graphallshortestpaths其语法如下 参数含义 G:稀疏矩阵 0/false代表无向图 1/true代表有向图。默认为true。
我们要解决如下问题 首先创建一个有向图
代码
clear all
clc
G sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],[41 99 51 32 15 45 38 32 36 29 21])
view(biograph(G,[],ShowWeights,on))
运行结果 第二步找出有向图中每对节点之间的所有最短路径。
使用graphallshortestpaths函数只需要加一行代码即可
clear all
clc
G sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],[41 99 51 32 15 45 38 32 36 29 21])
view(biograph(G,[],ShowWeights,on))
%添加代码如下
graphallshortestpaths(G)
运行结果 那返回的结果什么意思呢 比如说第一行代表的意思就是节点一分别到节点六的距离。为什么第一个值为0节点一到节点一当然在原位置了肯定为0咯。第二行类似一样的道理。因此从节点一到节点六最短距离为多少呢最短距离为95可以从返回表中一眼看出来。留个问题节点二到节点一位111怎么得到的路径位 根据结果推路径 第一行推出节点一先到节点五此时距离为21为么选节点五因为节点一到节点五最短,每次都选择最短 然后我们再跳到第五行节点五要先到节点四距离为36 于是我们再跳到第四行节点四要先到节点六距离为38 此时我们已经完成节点一到节点六距离为 21363895 路径为1—5—4—6 下面我在介绍一个新的方法会更简单 2.1.3 有向图最短路径2
保存该函数dijkstra.m你不需要修改知道这个函数具体意思我们调用它就行
function [min,path]dijkstra(w,start,terminal)
nsize(w,1); label(start)0; f(start)start;
for i1:nif i~startlabel(i)inf;
end, end
s(1)start; ustart;
while length(s)nfor i1:nins0;for j1:length(s)if is(j)ins1;endendif ins0vi;if label(v)(label(u)w(u,v))label(v)(label(u)w(u,v)); f(v)u;end endend
v10;kinf;for i1:nins0;for j1:length(s)if is(j)ins1;endendif ins0vi;if klabel(v)klabel(v); v1v;endendends(length(s)1)v1; uv1;
end
minlabel(terminal); path(1)terminal;
i1;
while path(i)~startpath(i1)f(path(i));ii1 ;
end
path(i)start;
Llength(path);
pathpath(L:-1:1);
然后现在我们再来解决一次上面同样的问题 比如求一到六节点最短路径
% 构造邻接矩阵
a zeros(6);
a sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],[41 99 51 32 15 45 38 32 36 29 21])
a a a;
a(a0) inf; % 零元素换成inf
a(eye(6,6)1)0; % 对角线换成 0
view(biograph(a,[],ShowWeights,on))
[min,path]dijkstra(a,1,6) % dijkstra模型求解节点一到节点六最短路径
输出 min就是最短路径为82路径过程为1 5 3 6
同样是求最短路径该方法可能更简单你只需要在这里创建一个矩阵可以求任意两个节点的最短距离和路径。请领悟一下在你的博客写好记录。 2.1.4 无向图最短路径1
还是求解这个问题 我们先用上面的第一种方法求
clear all
clc
W [41 99 51 32 15 45 38 32 36 29 21];
G sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W)
UG tril(G G)
view(biograph(UG,[],ShowArrows,off,ShowWeights,on))输出 然后添加一行代码使用求函数graphallshortestpaths注意这个函数2021版本被弃用
clear all
clc
W [41 99 51 32 15 45 38 32 36 29 21];
G sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W);
UG tril(G G)
view(biograph(UG,[],ShowArrows,off,ShowWeights,on))
graphallshortestpaths(UG,directed,false)
输出 我们可以一样就看出节点一到节点六最短距离82.
用我上面的讲过的方法可以看出路径为1-5-3-6 213229532982
2.1.5无向图最短路径2
其实我们可以使用函数shortestpath求解更方便
clc
clear all
% 构造邻接矩阵
G zeros(6);
G graph([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],[41 99 51 32 15 45 38 32 36 29 21])plot(G,EdgeLabel,G.Edges.Weight)
[P,d] shortestpath(G,1,6)
输出 p就是路径d就是最短距离更方便了
