超全的图论程序
关注微信公众号“超级数学建模”，教你做有料、有趣的数模人
程序一：可达矩阵算法
function P=dgraf(A)
n=size(A,1);
P=A;
for i=2:n
P=P+A^i;
end
P(P~=0)=1;
P;
程序二：关联矩阵和邻接矩阵互换算法
function W=incandadf(F,f)
if f==0
m=sum(sum(F))/2;
n=size(F,1);
W=zeros(n,m);
k=1;
for i=1:n
for j=i:n
if F(i,j)~=0
W(i,k)=1;
W(j,k)=1;
k=k+1;
end
end
end
elseif f==1
m=size(F,2);
n=size(F,1);
W=zeros(n,n);
for i=1:m
a=find(F(:,i)~=0);
W(a(1),a(2))=1;
W(a(2),a(1))=1;
end
else
fprint('Please imput the right value of f');
end
W;
程序三：有向图关联矩阵和邻接矩阵互换算法
function W=mattransf(F,f)
if f==0
m=sum(sum(F));
n=size(F,1);
W=zeros(n,m);
k=1;
for i=1:n
for j=i:n
if F(i,j)~=0
W(i,k)=1;
W(j,k)=-1;
k=k+1;
end
end
end
elseif f==1
m=size(F,2);
n=size(F,1);
W=zeros(n,n);
for i=1:m
a=find(F(:,i)~=0);
if F(a(1),i)==1
W(a(1),a(2))=1;
else
W(a(2),a(1))=1;
end
end
else
fprint('Please imput the right value of f'); end
W;
第二讲：最短路问题
程序一：Dijkstra算法（计算两点间的最短路）
function [l,z]=Dijkstra(W)
n = size (W,1);
for i = 1 :n
l(i)=W(1,i);
z(i)=0;
end
i=1;
while i<=n
for j =1 :n
if l(i)>l(j)+W(j,i)
l(i)=l(j)+W(j,i);
z(i)=j-1;
if ji=j-1;
end
end
end
i=i+1;
end
程序二：floyd算法（计算任意两点间的最短距离）
function [d,r]=floyd(a)
n=size(a,1);
d=a;
for i=1:n
for j=1:n
r(i,j)=j;
end
end
r;
for k=1:n
for i=1:n
for j=1:n
if d(i,k)+d(k,j)d(i,j)=d(i,k)+d(k,j); r(i,j)=r(i,k);
end
end
end
end
程序三：n2short.m 计算指定两点间的最短距离function [P u]=n2short(W,k1,k2)
n=length(W);
U=W;
m=1;
while m<=n
for i=1:n
for j=1:n
if U(i,j)>U(i,m)+U(m,j)
U(i,j)=U(i,m)+U(m,j);
end
end
end
m=m+1;
end
u=U(k1,k2);
P1=zeros(1,n);
k=1;
P1(k)=k2;
V=ones(1,n)*inf;
kk=k2;
while kk~=k1
for i=1:n
V(1,i)=U(k1,kk)-W(i,kk);
if V(1,i)==U(k1,i)
P1(k+1)=i;
kk=i;
k=k+1;
end
end
end
k=1;
wrow=find(P1~=0);
for j=length(wrow):-1:1
P(k)=P1(wrow(j));
k=k+1;
end
P;
程序四、n1short.m(计算某点到其它所有点的最短距离)
