数学建模入门之图论dijkstra

浅夏110

[color=rgba(0, 0, 0, 0.75)]数学建模入门之图论dijkstra
0 b( D) q1 {  [/ ^
# d4 h1 m; @# P+ y& N) I
; _; V/ `+ P4 u3 k2 r
$ b  A" Y4 I! N+ Z. L4 f) h2 H" W
! b! Z% U& t4 n  _

程序名为：tulun1.m

% 本程序为主程序，请进行修改。weight=[0     8   Inf   Inf   Inf   Inf     7     8   Inf   Inf   Inf;   Inf     0     3   Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf;   Inf   Inf     0     5     6   Inf     5   Inf   Inf   Inf   Inf;   Inf   Inf   Inf     0     1   Inf   Inf   Inf   Inf   Inf    12;   Inf   Inf     6   Inf     0     2   Inf   Inf   Inf   Inf    10;   Inf   Inf   Inf   Inf     2     0     9   Inf     3   Inf   Inf;   Inf   Inf   Inf   Inf   Inf     9     0   Inf   Inf   Inf   Inf;     8   Inf   Inf   Inf   Inf   Inf   Inf     0     9   Inf   Inf;   Inf   Inf   Inf   Inf     7   Inf   Inf     9     0     2   Inf;   Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf     2     0     2;   Inf   Inf   Inf   Inf    10   Inf   Inf   Inf   Inf   Inf     0;];% 我们修改的就是邻接矩阵的值[dis, path]=dijkstra(weight,1, 11)% 1，11，分别代表起始点，如果我们要求2到8的最短距离，则更改为2-8即可。

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
  , V6 @1 J0 v; c$ W% L$ c- r, `

本程序名为dijkstra.m

% 求一个顶点到另一个定点的最短路径，实际上能求从出发点到其他所有节点的最短路径。% 修改的是带权邻接矩阵：% [0 1 3     v1:v1的距离是0，v1:v2的距离是1， v1:v3的距离是3，v2:v1的距离是1，v2:v2的距离是2%   1 0 2   距离无穷的为Inf% 本程序为子程序，请找tulun1修改主程序。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, ends(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;endmin=label(terminal); path(1)=terminal;i=1; while path(i)~=start      path(i+1)=f(path(i));      i=i+1 ;endpath(i)=start;L=length(path);path=path(L:-1:1);
! H; d; S) b' ~3 `* t