3路径最短路径最大流Word格式文档下载.docx
- 文档编号:1208207
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:19
- 大小:183.61KB
3路径最短路径最大流Word格式文档下载.docx
《3路径最短路径最大流Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《3路径最短路径最大流Word格式文档下载.docx(19页珍藏版)》请在冰点文库上搜索。
%从栈顶取出当前位置loc,访问过的方向编号f
loc=path(end,1:
2);
f=path(end,3);
iff==4
path(end,:
)=[];
%尝试了所有的方向之后,出栈
else
path(end,3)=f+1;
nextloc=loc+FS(f+1,:
);
%下一步的位置nextloc
ifnextloc
(1)>
=1&
nextloc
(1)<
=m&
nextloc
(2)>
nextloc
(2)<
=n&
MG(nextloc
(1),nextloc
(2))==0
path=[path;
nextloc0];
%进栈
ifnextloc
(1)==t
(1)&
nextloc
(2)==t
(2)
path=path(:
1:
return;
end
end
end
分析:
迷宫A、迷宫D,找出一条路径。
迷宫B、迷宫C,陷入死循环!
原因:
未考虑走回头路的可能性!
1.3求一条简单路径(检查足迹)
MG(nextloc
(1),nextloc
(2))==0&
isIn(path,nextloc)==0
functionF=isIn(path,loc)
fori=1:
size(path,1)
ifpath(i,1)==loc
(1)&
path(i,2)==loc
(2)
F=1;
F=0;
迷宫A、迷宫B、迷宫C、迷宫D,找出一条路径,但未必是最短路径。
归纳:
图缺少明确的层次性,在遍历时,完全有可能访问已经访问过的顶点(位置/状态)。
思考:
有无其他检查足迹的方法?
当然有!
1.4求所有简单路径
functionfindMGPaths(MG,s,t)
path(:
2)%显示所有路径
思考:
虽然能输出所有路径,但更希望保存所有的路径,以便进一步计算。
2带权图中单点到单点的路径
2.1示例数据:
有向图
有向无环图
有向有环图
G=[032000
001340
000020
000002
000003
000000];
001310
030003
目标:
求出一条简单路径。
若无路径,则路径为空。
path=FindPath(G,1,6)
注意:
要检查足迹。
2.2从起点到终点的路径(非递归算法)
functionpath=FindPath(G,s,t);
%路径栈
%从栈顶取出当前位置v,访问过的邻接点下标f
v=path(end,1);
f=path(end,2);
adjv=find(G(v,f+1:
end)>
0)+f;
%+f细节决定胜负
ifisempty(adjv)
%尝试了所有邻接点后,出栈
nextadjv=adjv
(1);
%下一个邻接点adjv
path(end,2)=nextadjv;
ifisempty(find(path(:
1)==nextadjv))%检查足迹
nextadjv0];
ifnextadjv==t%找到了终点
1);
测试:
path=FindPath(G,1,6)有路径
path=FindPath(G,1,8)无路径
2.3思考:
从起点到终点的所有路径
2.4从起点到终点的路径(递归算法)
functiontestPath
globalGpathpaths
paths=[];
path=[];
FindPath(1,6);
paths
functionFindPath(s,t);
globalGpathpaths
s];
ifs==t
paths(end+1).path=path%保存所有路径
else
adjv=find(G(s,:
)>
0);
%所有的邻接点
length(adjv)
ifisempty(find(path==adjv(i)))
%以未被访问过的邻接点为起点,进行深度优先搜索
FindPath(adjv(i),t);
path(end)=[];
%出栈
算法检验:
所求路径中当然没有回路!
所有路径
1,2,3,5,6
1,2,4,6
1,2,5,6
1,3,5,6
1,3,5,2,4,6
3归纳与提高
3.1归纳
图的遍历的功能:
从指定顶点出发,遍历图中每个顶点。
深度优先搜索DFS算法的特征是:
以未被访问过的邻接点为起点,进行DFS。
核心数据结构:
栈。
实现形式:
可递归,可非递归。
3.2提高:
欧拉回路
算法步骤:
1、利用DFS,从图中求得任一回路;
若无回路,则原图非欧拉图;
2、从图中删掉回路中的边;
3、若图中的边集不为空,转步骤1,否则转步骤4;
4、组合所有的回路,即得到欧拉回路。
C1=[5125]
C2=[32463]
C3=[874138]
练习1:
将上述DFS函数改为求一条回路的函数。
练习2:
如何将上述C1、C2、C3合并为一条回路。
4单点到多点的最短路径算法
4.1无权图的最短路径算法
计算从v3到其余各个顶点的最短路径。
functiontestBFS
G=[
0101000
0001100
1000010
0010111
0000001
0000000
0000010];
sd=BFS(G,3)%sd=[1202313]
广度优先搜索BFS算法的特征是:
从起点由近及远,访问未被访问过的顶点。
队列。
%队列的示例:
%3162%第1行是节点下标,
%0112%第2行是节点对应的最短路径长度
每个顶点只能进一次队列。
同样要防备顶点重复进队列。
引入标志向量flag。
flag(i)==0表示顶点i未进队列
flag(i)==1表示顶点i已进队列
functionsd=BFS(G,sv)
n=size(G,1);
flag=zeros(1,n);
%标志向量
sd=ones(1,n)*inf;
sd(sv)=0;
%初始化sd为[infinf0infinfinfinf]
Q=[sv;
0];
flag(sv)=1;
%队列Q初始化
while~isempty(Q)
v=Q(1,1);
d=Q(2,1);
sd(v)=d;
%填写最短路径长度
Q(:
1)=[];
%出队列
adjv=find(G(v,:
)==1);
%找到v的所有邻接点adjv
adjv=adjv(find(flag(adjv)==0));
%adjv没有进过队列的邻接点
adjvsd=ones(1,length(adjv))*(d+1);
Q=[Q(1,:
)adjv;
Q(2,:
)adjvsd];
%进队列
flag(adjv)=1;
只求出了最短路径长度,如何表示、计算最短路径?
4.2带非负权图的最短路径
Dijkstra算法:
基于贪心规则,从起点由近及远,利用三角不等式,逐步修正从起点到各个顶点的最短路径。
标志向量Finish,表示对应顶点的最短路径长度已经确定。
Cost=[0,Inf,10,Inf,30,100;
Inf,0,5,Inf,Inf,Inf;
Inf,Inf,0,50,Inf,Inf;
Inf,Inf,Inf,0,Inf,10;
Inf,Inf,Inf,20,0,60;
Inf,Inf,Inf,Inf,Inf,0
];
sv=1;
[Dist,Path]=Dijkstra(Cost,sv)
forev=1:
length(Path)
Display(Path,sv,ev)
计算最短路径长度,并保存每个最短路径中的上一个顶点。
function[Dist,Path]=Dijkstra(Cost,StartV)
n=size(Cost,1);
%顶点个数
Dist=Cost(StartV,:
%路径长度初始化为邻边长度
Path=zeros(1,n);
%路径初始化为全0
Finish=zeros(1,n);
Finish(StartV)=1;
n-1
w=MinCost(Dist,Finish);
%最近的邻接点w(尚未确定最短距离)
if(w==0)return;
end;
Finish(w)=1;
forj=1:
n
if(Finish(j)==0&
&
Dist(w)+Cost(w,j)<
Dist(j))%三角不等式
Dist(j)=Dist(w)+Cost(w,j);
Path(j)=w;
%只记住到达j之前的中间顶点
%查找Finish(i)==0的Dist(i)中的最小值的下标
functionimin=MinCost(Dist,Finish)
min=inf;
imin=0;
length(Dist)
if(Finish(i)==0&
Dist(i)<
min)
min=Dist(i);
imin=i;
%组合出sv->
ev的顶点序列
functionpathv=Display(Path,sv,ev)
v=ev;
pathv=[v];
whilePath(v)>
v=Path(v);
pathv=[vpathv];
pathv=[svpathv];
4.3带负权图的最短路径
能否有最省事的方法求解带负权图的最短路径?
functiontestNegBFS
G=[02-20
0000
0002
0100];
%-10100];
sd=NegBFS(G,1)%sd=[01-20]
BellmanFord算法:
基于穷举的思路,从起点由近及远,利用三角不等式,逐步修正从起点到各个顶点的最短路径。
算法框架:
利用BFS算法的框架,实现穷举所有邻接边的效果。
标志向量flag,表示对应顶点是否进过队列,而非路径长度已经确定。
functionsd=NegBFS(G,sv)
%初始化sd为[0infinfinf]
Q=[sv];
v=Q
(1);
Q
(1)=[];
)~=0);
w=adjv(i);
%邻接点的下标w
ifsd(v)+G(v,w)<
sd(w)
sd(w)=sd(v)+G(v,w)
ifflag(w)==0
Q=[Qw];
flag(w)=1;
5时间轴上的有向图
5.1拓扑排序
5.2分阶段的拓扑排序
5.3关键路径
6最大流
6.1网络流的应用背景
存储结构
计算s->
t的最大流量。
functiontestFlow
mount=Flow(G,1,6)%mount=5
6.2网络流的算法
6.2.1算法思路
1、找到从s->
t的一条路径
2、找到该路径的流量(组成各边流量的最小值)
3、从图中删除该流量
4、重复步骤1至3,直至s->
t无路径。
6.2.2演算示例
示例1:
第1条路径
第2条路径
第3条路径
依次找到的路径
删除路径流量后的剩余图
太简洁了,似乎有点不安全感。
问:
路径的次序如何定义?
不同的次序对结果有无影响?
示例2:
找到的第1条路径
6.2.3演算改进与细化
深入理解有向图的结构:
示例:
6.2.4算法实现
functionmount=Flow(G,s,t);
mount=0%总流量
while1
G
path=FindPath(G,s,t);
%[12356]
ifisempty(path)break;
vs=[path(1:
end-1)'
path(2:
end)'
];
%路径中的边集合
vsdist=[];
length(vs)
vsdist(i)=G(vs(i,1),vs(i,2));
pathmount=min(vsdist);
%路径流量
mount=mount+pathmount;
G(vs(i,1),vs(i,2))=G(vs(i,1),vs(i,2))-pathmount;
G(vs(i,2),vs(i,1))=G(vs(i,2),vs(i,1))+pathmount;
6.3实际应用
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 路径 最大