matlab练习程序（单源最短路径Dijkstra）

￡神魔★判官ぃ 2021-12-16 10:35 306阅读 0赞

图的相关算法也算是自己的一个软肋了，当年没选修图论也是一大遗憾。

图像处理中，也有使用图论算法作为基础的相关算法，比如图割，这个算法就需要求最大流、最小割。所以熟悉一下图论算法对于图像处理还是很有帮助的。

Dijkstra和Bellman-Ford类似，都是解决单源最短路径问题，不同的是这个方法只能解决边为非负的问题，实现的好的Dijkstra算法运行时间要快于Bellman-ford。

算法步骤如下：

1.首先设置队列，所有节点入列，源节点值为0，其他节点值为无穷。

2.然后在队列中找值最小的节点并出列。

3.计算出列的节点所有后继节点的距离。

4.松弛方法，如果新计算的距离小于上次计算的距离，那么更新距离，即将后继节点值设为较小的距离，并将后继节点的前趋设为当前的出列节点。

5.对剩余的节点队列继续找最小值并出列，不断循环2、3、4步直到队列中没有节点了。

步骤是上面没错，不过我程序中没有完全按照上述的步骤实现。不同的地方在于我没有做出列操作，而是通过标记节点的形式实现的。

运行结果如下，图（是图不是图片）是算法导论367页上的：

![10105812-802536958d5049b1883ee34750c1ad8f.jpg][]

![10105852-1956271e1ab04f75b9bfee39e021b3f0.jpg][]

matlab代码如下，netplot和compresstable2matrix和[上一篇][Link 1]使用的一样：

main.m

clear all;close all;clc
    %初始化邻接压缩表，1 2 10 表示从节点1到节点2，边的权重为10
    b=[1 2 10;1 4 5;2 3 1;
       2 4 2; 3 5 4;4 2 3;
       4 3 9; 4 5 2;5 1 7;
       5 3 6];
    
    m=max(max(b(:,1:2)));       %压缩表中最大值就是邻接矩阵的宽与高
    A=compresstable2matrix(b);  %从邻接压缩表构造图的矩阵表示
    netplot(A,1)                %形象表示
    
    S=inf(1,m);         %从开始的源点到每一个节点的距离
    S(1)=0;             %源点到自己的距离为0
    pa=zeros(1,m);      %存储每个节点的前驱，在松弛过程中赋值
    pa(1)=1;　　　　　　　%源点的前趋是自己　
    
    visit=zeros(1,m);   %标记某个节点是否访问过了
    index=1;            %从index节点开始搜索        
    
    %判断是否对所有节点都找的最短路径了。可能会有源点没有路径到目标节点的情况，那就无限循环了
    while sum(visit)~=m    %没有出队列操作，不过通过visit来等价的表示了
        
        visit(index)=1;                     %标记第index节点为已入列的节点
        [S pa]=relax(S,pa,A,visit,index,m);         %松弛，如果两个节点间有更短的距离，则用更短的距离
        index=extract_min(S,visit,index,m); %使用已访问的最小的节点作为下一次搜索的开始节点  
    
    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)                %形象表示

relax.m

%边缘松弛，使用更短的距离作为节点的值
    function [S pa]=relax(S,pa,A,visit,index,m)
       
       i=index;
       for j=1:m
            if A(i,j)~=inf && visit(j)~=1   %搜索没有标记过的节点
                if S(j)>S(i)+A(i,j)         %将较小的值赋给正在搜寻的节点
                    S(j)=S(i)+A(i,j);
                    pa(j)=i;
                end
            end        
        end    
    
    end

extract\_min.m

%提取队列中尚未标记的最小的值的序号
    function index=extract_min(S,visit,index,m)
    
        Mi=inf;
        for j=1:m
            if visit(j)~=1
               if S(j)<Mi
                    Mi=S(j);
                    index=j;
               end
            end
        end    
    
    end

转载于:https://www.cnblogs.com/tiandsp/p/3182034.html

[10105812-802536958d5049b1883ee34750c1ad8f.jpg]: /images/20211214/ef393e64952344c5a26eddf7ea2d3a6d.png
[10105852-1956271e1ab04f75b9bfee39e021b3f0.jpg]: /images/20211214/b52f79bd91454f03ae2156bd0962cd47.png
[Link 1]: http://www.cnblogs.com/tiandsp/p/3181596.html