数学建模社区-数学中国

标题: 数学建模入门之图论dijkstra [打印本页]

作者: 浅夏110 时间: 2018-11-2 08:57
标题: 数学建模入门之图论dijkstra
[color=rgba(0, 0, 0, 0.75)]数学建模入门之图论dijkstra

程序名为：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
! U9 y% ?' O" g% t

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

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)