数学建模入门之图论dijkstra

浅夏110

[color=rgba(0, 0, 0, 0.75)]数学建模入门之图论dijkstra

" ?2 J! M. u) l9 b) Z
2 R3 ~" |; x/ \7 d; I
# j1 P8 ^/ z+ w4 v& r

程序名为：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
  - u! V7 q) E" ]8 f

本程序名为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);

' V# R% C& m  U- [$ L+ u