matlab计算最短路径讲述.docx
- 文档编号:15412093
- 上传时间:2023-07-04
- 格式:DOCX
- 页数:12
- 大小:70KB
matlab计算最短路径讲述.docx
《matlab计算最短路径讲述.docx》由会员分享,可在线阅读,更多相关《matlab计算最短路径讲述.docx(12页珍藏版)》请在冰点文库上搜索。
matlab计算最短路径讲述
湖南大学
MATLAB实训报告
题目:
matlab计算最短路径问题
学院名称:
信息科学与工程学院
专业班级:
软件工程四班
学生姓名:
彭天越
学号:
20112601416
日期:
2013年7月3号
题目
求下图中顶点ν1到顶点ν11的最短距离和最短路(2学分)
B.有向图
问题描述
(1)根据无向图A,使用Di.jistra算法
(2)根据有向图B,使用Warshall-Floyd算法
思路及代码
(1)思路
(1)Dijkstra算法
使用范围:
1)寻求从一固定顶点到其余各点的最短路径;
2)有向图、无向图和混合图;
3)权非负.
算法思路:
采用标号作业法,每次迭代产生一个永久标号,从而生长一颗以v0为根的最短路树,在这颗树上每个顶点与根节点之间的路径皆为最短路径.
诉法步骤:
S:
具有永久标号的顶点集;
l(v):
v的标记;f(v):
v的父顶点,用以确定最短路径;
输入加权图的带权邻接矩阵w=[w(vi,vj)]nxm.
1)初始化令l(v0)=0,S=F;"v¹v0,l(v)=¥;
2)更新l(v),f(v)
寻找不在S中的顶点u,使l(u)为最小.把u加入到S中,然后对所有不在S中的顶点v,如l(v)>l(u)+w(u,v),则更新l(v),f(v),即l(v)¬l(u)+w(u,v),f(v)¬u;
3)重复步骤2),直到所有顶点都在S中为止.
(2)Floyd算法
使用范围:
1)求每对顶点的最短路径;
2)有向图、无向图和混合图;
算法思想:
直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D
(1),D
(2),…,D(n),D(n)是图的距离矩阵,同时引入一个后继点矩阵记录两点间的最短路径.
算法步骤:
d(i,j):
i到j的距离;
path(i,j):
i到j的路径上i的后继点;
输入带权邻接矩阵a(i,j).
1)赋初值
对所有i,j,d(i,j)¬a(i,j),path(i,j)¬j,k=l.
2)更新d(i,j),path(i,j)
对所有i,j,若d(i,k)+d(k,j) d(i,j)¬d(i,k)+d(k,j),path(i,j)¬path(i,k),k¬k+1 3)重复2)直到k=n+1 (2)源代码 (1)Dijkstra.m文件 %计算最短路径(Dijkstra算法) %min表示最短的距离 %path表示最短路径 %w表示邻接矩阵 %start表示开始点 %terminal表示终止点 function[min,path]=dijkstra(w,start,terminal) n=size(w,1);%计算邻接矩阵的行数 label(start)=0;f(start)=start; %初始化 fori=1: n ifi~=start label(i)=inf; end end s (1)=start;u=start; %更新最短路径直到所有顶点都遍历 whilelength(s) fori=1: n ins=0; forj=1: length(s) ifi==s(j) ins=1; end end ifins==0 v=i; iflabel(v)>(label(u)+w(u,v)) label(v)=(label(u)+w(u,v)); f(v)=u; end end end % v1=0; k=inf; fori=1: n ins=0; forj=1: length(s) ifi==s(j) ins=1; end end ifins==0 v=i; ifk>label(v) k=label(v); v1=v; end end end s(length(s)+1)=v1; u=v1; end %求出最短距离与最短路径 min=label(terminal);path (1)=terminal; i=1; whilepath(i)~=start path(i+1)=f(path(i)); i=i+1; end path(i)=start; L=length(path); path=path(L: -1: 1);%循环输出路径 text01.m脚本文件进行测试 clear; clc; fprintf('计算最短路径(Dijkstra算法)\n'); x=[0,2,1,8,inf,inf,inf,inf,inf,inf,inf; 2,0,inf,6,1,inf,inf,inf,inf,inf,inf; 1,inf,0,7,inf,inf,9,inf,inf,inf,inf; 8,6,7,0,5,1,2,inf,inf,inf,inf; inf,1,inf,5,0,3,inf,2,1,inf,inf; inf,inf,inf,1,3,0,4,inf,6,inf,inf; inf,inf,9,2,inf,4,0,inf,3,1,inf; inf,inf,inf,inf,2,inf,inf,0,7,inf,inf; inf,inf,inf,inf,inf,6,3,7,0,1,2; inf,inf,inf,inf,inf,inf,1,inf,1,0,1; inf,inf,inf,inf,inf,inf,inf,inf,2,1,0] %x=input('输入邻接矩阵: '); start=input('输入起点: '); terminal=input('输入终点: '); fprintf('计算结果如下: '); [min,path_way]=dijkstra(x,start,terminal) Floyd.m函数 %计算最短路径(Floyd算法) %[D,path,min1,path1]=floyd(a,start,terminal)返回矩阵D,path;并返回start与terminal之间的最短距离min1和最短路径path1. %path(i,j): 表示i到j的路径上i的后继点; %D(i,j): 表示i到j的距离; %输入带权邻接矩阵a(i,j). %1)赋初值 %对所有i,j,D(i,j)<-a(i,j),path(i,j)<-j %2)更新D(i,j),path(i,j) %对所有i,j,若D(i,k)+D(k,j) %D(i,j)<-D(i,k)+D(k,j),path(i,j)<-path(i,k),k<-k+1 %3)重复2)直到k=n+1 function[D,path,min1,path1]=floyd(a,start,terminal) D=a; n=size(D,1); path=zeros(n,n);%初始化 fori=1: n forj=1: n ifD(i,j)~=inf path(i,j)=j; end end end fork=1: n fori=1: n forj=1: n ifD(i,k)+D(k,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end end end end ifnargin==3%参数个数为3的时候执行 min1=D(start,terminal);%最短距离 m (1)=start; i=1; path1=[];%计算最短路径 whilepath(m(i),terminal)~=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m; end text02.m脚本文件,进行测试 clear; clc; fprintf('计算最短路径(Floyd算法)\n'); x=[0,2,inf,8,inf,inf,inf,inf,inf,inf,inf; inf,0,inf,6,1,inf,inf,inf,inf,inf,inf; 1,inf,0,inf,inf,inf,9,inf,inf,inf,inf; inf,inf,7,0,inf,inf,inf,inf,inf,inf,inf; inf,inf,inf,5,0,inf,inf,inf,1,inf,inf; inf,inf,inf,1,3,0,4,inf,inf,inf,inf; inf,inf,inf,2,inf,inf,0,inf,3,1,inf; inf,inf,inf,inf,2,inf,inf,0,inf,inf,inf; inf,inf,inf,inf,inf,6,inf,7,0,inf,inf; inf,inf,inf,inf,inf,inf,inf,inf,1,0,1; inf,inf,inf,inf,inf,inf,inf,inf,2,inf,0] %x=input('输入邻接矩阵: '); start=input('输入起点: '); terminal=input('输入终点: '); fprintf('计算结果如下: '); [D,path,min,path_way]=floyd(x,start,terminal) 测试结果说明 (1)Di.jistra算法 根据无向图A,可以知道matlab计算出来的结果是正确的 (2)Floyd算法 根据有向图B,可以知道matlab计算出来的结果是正确的 小结 Matlab现在的发展已经使其成为一种集数值运算、符号运算、数据可视化、图形界面设计、程序设计、仿真、图像处理、电路设计等多种功能于一体的集成化软件,在矩阵方面等处理占据很大的优势,图论中的很多问题均能通过matlab来解决,方便而高效,比如哥尼斯堡七桥问题,连通性邻接矩阵等概念的提出,更便于解决图论中的计算最短路径的问题,要熟练掌握一门语言,乃至精通就必须要多练多动手自己多思考,然后要懂得充分的利用可靠资源!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- matlab 计算 路径 讲述