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来解决，方便而高效，比如哥尼斯堡七桥问题，连通性邻接矩阵等概念的提出，更便于解决图论中的计算最短路径的问题，要熟练掌握一门语言，乃至精通就必须要多练多动手自己多思考，然后要懂得充分的利用可靠资源！
升级会员 