matlab练习程序(单源最短路径Bellman-Ford)

2014年1月12日 09:50
转载(0) / 评论(0) / 浏览(978)

该算法可以用来解决一般(边的权值为负)的单源最短路径问题,而dijkstra只能解决权值非负的情况。

此算法使用松弛技术,对每一个顶点,逐步减少源到该顶点的路径的估计值,直到达到最短的路径。

算法运算结果:

\

\

matlab代码如下,netplot函数在这里,不过当时函数中表示两节点没有路径用的是0,而现在需要改成inf:

clear all;close all;clc
%初始化邻接压缩表
b=[1 2 6;
4 7 
3 5;
4 8;
5 -4;
2 -2;
3 -3;
5 9;
1 2;
3 7];

m=max(max(b(:,1:2)));            %压缩表中最大值就是邻接矩阵的宽与高
A=compresstable2matrix(b);  %从邻接压缩表构造图的矩阵表示
netplot(A,1)                %形象表示

S=inf(1,m);                 %源到其他节点的最短距离,开始为inf
S(1)=0;                     %源点到自己的距离为0
pa=zeros(1,m);              %寻找到的节点的前趋
pa(1)=1;                    %源点的前趋是自己

pre_pa=ones(1,m);
while sum(pre_pa==pa)~=m    %终止条件,判断终止的方法很多,这个应该不是最佳实践
    pre_pa=pa;
    for k=1:m
        if pre_pa(k)~=0                 %对每一个已搜寻到的节点,从此节点寻找后继节点
            i=k;                
            for j=1:m
                if A(i,j)~=inf
                    if S(j)>S(i)+A(i,j)
                        S(j)=S(i)+A(i,j);       %边缘松弛,取两节点间最小权值作为实际权值
                        pa(j)=i;                %寻找前趋
                    end
                end
            end
         end
    end
end
%最终我们需要的就是这两个值
S       %源点到其他每一点的距离
pa      %其他每一节点的前趋

%算法到此结束,下面只是为了形象的表示而写的。
re=[];
for i=2:m
    re=[re;pa(i) i A(pa(i),i)];
end
A=compresstable2matrix(re);  %从邻接压缩表构造图的矩阵表示
figure;
netplot(A,1)                %形象表示


 compresstable2matrix.m  

function A=compresstable2matrix(b)
    [n ~]=size(b);
    m=max(max(b(:,1:2)));
    A=inf(m,m);

    for i=1:n
        A(b(i,1),b(i,2))=b(i,3);
    end

end


评论(0)

发表评论
登录
我可以
  • 评论
关联标签
Matlab × 12
关联热门电子辑
类似的技文

浏览(778) / 评论(0) / 2014年1月12日 09:52

浏览(795) / 评论(0) / 2014年1月12日 09:55

浏览(789) / 评论(0) / 2013年9月30日 22:27

浏览(772) / 评论(0) / 2014年1月12日 10:09

浏览(503) / 评论(0) / 2013年9月30日 22:27

浏览(838) / 评论(0) / 2014年1月13日 09:11

浏览(823) / 评论(0) / 2014年1月13日 09:13

浏览(3) / 评论(0) / 2014年1月10日 10:16

浏览(1012) / 评论(0) / 2014年1月13日 09:14