图的最短路径问题
问题描述
Matlab求解最短路径
s = [9 9 1 1 2 2 2 7 7 6 6 5 5 4];
t = [1 7 7 2 8 3 5 8 6 8 5 3 4 3];
w = [4 8 3 8 2 7 4 1 6 6 2 14 10 9];
G = graph(s,t,w);
plot(G, ‘EdgeLabel‘, G.Edges.Weight, ‘linewidth‘, 2)
set( gca, ‘XTick‘, [], ‘YTick‘, [] );
[P,d] = shortestpath(G, 9, 4) %注意：该函数matlab2015b之后才有哦 P里面存储的就是最短路径上面的节点
% 在图中高亮我们的最短路径
myplot = plot(G, ‘EdgeLabel‘, G.Edges.Weight, ‘linewidth‘, 2); %首先将图赋给一个变量
highlight(myplot, P, ‘EdgeColor‘, ‘r‘) %对这个变量即我们刚刚绘制的图形进行高亮处理（给边加上r红色）
% 求出任意两点的最短路径矩阵
D = distances(G) %注意：该函数matlab2015b之后才有哦
D(1,2) % 1 -> 2的最短路径
D(9,4) % 9 -> 4的最短路径
% 找出给定范围内的所有点 nearest(G,s,d)
% 返回图形 G 中与节点 s 的距离在 d 之内的所有节点
[nodeIDs,dist] = nearest(G, 2, 10) %注意：该函数matlab2016a之后才有哦
求最短路径算法
求解最短路径算法主要包括迪杰斯特拉算法和弗洛伊德算法
强烈推荐观看视频：图论最短距离(Shortest Path)算法动画演示-Dijkstra(迪杰斯特拉)和Floyd(弗洛伊德)_哔哩哔哩_bilibili
迪杰斯特拉算法的matlab实现
function [mydistance,mypath]=mydijkstra(a,sb,db);
%输入：a——邻接矩阵；a(i,j)——i到j之间的距离，可以是有向的
%sb——起点的标号，db——终点的标号
%输出：mydistance——最短路的距离，mypath——最短路的路径
n=size(a,1);visited(1:0)=0;
distance(1:n)=inf;distance(sb)=0; %起点到各顶点距离的初始化
visited(sb)=1;u=sb; %u为最新的S集合顶点
parent(1:0)=0; %前驱顶点的初始化
for i=1:n-1
id=find(visited==0); %查找V-S集合的顶点
for v=id
if a(u,v)+distance(u)<distance(v)
distance(v)=distance(u)+a(u,v); %修改标号值
parent(v)=u;
end
end
temp=distance;
temp(visited==1)=inf; %已标号点的距离换成无穷大
[t,u]=min(temp); %找标号值最小的顶点
visited(u)=1; %标记已经标号的顶点
end
mypath=[];
if parent(db)~=0 %如果存在路！
t=db;mypath=[db];
while t~=sb
P=parent(t);
mypath=[P mypath];
t=P;
end
end
mydistance=distance(db);
弗洛伊德算法的matlab实现
function [dist,path]=myfloyd(a)
%寻找i,j两点最短路径
% 输入：a—邻接矩阵，元素(aij)是顶点i到j之间的直达距离，可以是有向的
% sb—起点的标号；db—终点的标号
% 输出：dist—最短路的距离；% path—最短路的路径
n=size(a,1);
m=a;
for i=1:n %path矩阵的初始化
for j=1:n
path(i,j)=j;
end
end
for k=1:n
for i=1:n
for j=1:n
if a(i,j)>a(i,k)+a(k,j)
a(i,j)=a(i,k)+a(k,j);
path(i,j)=k;
end
end
end
end
for sb=1:n
for db=1:n
t=path(sb,db);
dist(sb,db)=m(sb,t);
while t~=db
p=path(t,db);
dist(sb,db)=dist(sb,db)+m(t,db);
t=p;
end
end
end
最小生成树
连通赋权图的具有最小权的生成树叫做最小生成树
问题描述
求解最小生成树的算法有Kruskal(克鲁斯卡尔)和Prim(普里姆)算法：
观看视频：最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示_哔哩哔哩_bilibili
Kruskal算法matlab实现
%边权矩阵，每一列都表示一条边，从上到下分别为两个顶点以及它们边的权值
b = [1 1 1 2 2 3 3 4;
2 4 5 3 5 4 5 5;
8 1 5 6 7 9 10 3];
%sortrows函数对某一列进行比较排序，所以我们先转置b矩阵，然后对第三列也就是权值进行排序
[B,i]=sortrows(b‘,3);
%再将其转置回来
B=B‘;
%m为边的条数，n为点的个数
m=size(b,2);n=5;
%t数组用来标记选中的边，k用来计数，T矩阵用来存储选中的边，c计算最小生成树的总长度
t=1:n;k=0;T=[];c=0;
for i=1:m
if t(B(1,i))~=t(B(2,i))
k=k+1;T(k,1:2)=B(1:2,i),c=c+B(3,i);
tmin=min(t(B(1,i)),t(B(2,i)));
tmax=max(t(B(1,i)),t(B(2,i)));
for j=1:n
if t(j)==tmax
t(j)=tmin;
end
end
end
if k==n-1
break;
end
end
T,c,
来源：【MATLAB】最小生成树Kruskal算法_taoxing-CSDN博客_kruskal算法
Prim算法matlab实现
function [result]=myprim(a)//a为传入的每个点的距离矩阵
result=[];//用result（3×n）矩阵来表示，第一行表示起点，第二行表示终点，第三行表示权值
p=1;tb=2:length(a);
while size(result,2)~=length(a)-1
temp=a(p,tb);temp=temp(:);
d=min(temp);
[jb,kb]=find(a(p,tb) == d,1);
j=p(jb);k=tb(kb);
result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end
result第一行表示起点，第二行表示终点，第三行表示权值
来源：数模：最小生成树prim算法（通用matlab代码）_萌新的博客-CSDN博客_prim算法matlab代码