图论模型-di jkstra代码及使用方法

短命女 2022-02-02 14:36 227阅读 0赞

%dijkstra.m   编辑器文件
    function [min,path]=dijkstra(w,start,terminal)
    n=size(w,1); label(start)=0; f(start)=start;
    for i=1:n
       if i~=start
           label(i)=inf;
    end, end
    s(1)=start; u=start;
    while length(s)<n
       for i=1:n
          ins=0;
          for j=1:length(s)
             if i==s(j)
                ins=1;
             end,  
          end
          if ins==0
             v=i;
             if label(v)>(label(u)+w(u,v))
                label(v)=(label(u)+w(u,v)); 
             f(v)=u;
             end, 
          end, 
       end   
    v1=0;
       k=inf;
       for i=1:n
             ins=0;
             for j=1:length(s)
                if i==s(j)
                   ins=1;
                end, 
             end
             if ins==0
                v=i;
                if k>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; 
    while path(i)~=start
          path(i+1)=f(path(i));
          i=i+1 ;
    end
    path(i)=start;
    L=length(path);
    path=path(L:-1:1);

例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1clFR_size_16_color_FFFFFF_t_70]  
%命令窗口 或编辑框文件  
weight= \[0 2 8 1 Inf Inf Inf Inf Inf Inf Inf;  
2 0 6 Inf 1 Inf Inf Inf Inf Inf Inf;  
8 6 0 7 5 1 2 Inf Inf Inf Inf;  
1 Inf 7 0 Inf Inf 9 Inf Inf Inf Inf;  
Inf 1 5 Inf 0 3 Inf 2 9 Inf Inf;  
Inf Inf 1 Inf 3 0 4 Inf 6 Inf Inf;  
Inf Inf 2 9 Inf 4 0 Inf 3 1 Inf;  
Inf Inf Inf Inf 2 Inf Inf 0 7 Inf 9;  
Inf Inf Inf Inf 9 6 3 7 0 1 2;  
Inf Inf Inf Inf Inf Inf 1 Inf 1 0 4;  
Inf Inf Inf Inf Inf Inf Inf 9 2 4 0;\];  
\[dis, path\]=dijkstra(weight,1, 11)；  
% 第一个参数：带权邻接矩阵;第二个参数:起始点; 第二个参数: 终止点。  
% 这三个参数视情况需要改。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1clFR_size_16_color_FFFFFF_t_70]: /images/20220202/4d8378bae6de45c29bb939350666d7aa.png