暴强Dijkstra算法求任意两点间最短路径(matlab程序)

1、精品好资料学习推荐效果展示：开头输入的是点的序列号（表示第几个点），显示的是最短路径的走法（同样以点的序列号显示，表示途径的第几个点）。%编写m文件function distance,path=dijkstra(A,s,e)% DISTANCE,PATH=DIJKSTRA(A,S,E)% returns the distance and path between the start node and the end node.% A: adjcent matrix% s: start node% e: end node% initializen=size(A,1); % node number

2、D=A(s,:); % distance vectorpath=; % path vectorvisit=ones(1,n); % node visibilityvisit(s)=0; % source node is unvisibleparent=zeros(1,n); % parent node% the shortest distancefor i=1:n-1 % BlueSet has n-1 nodes temp=zeros(1,n); count=0; for j=1:n if visit(j) temp=temp(1:count) D(j); else temp=temp(1:

3、count) inf; end count=count+1; end value,index=min(temp); j=index; visit(j)=0; for k=1:n if D(k)D(j)+A(j,k) D(k)=D(j)+A(j,k); parent(k)=j; end endenddistance=D(e);% the shortest distance pathif parent(e)=0 return;endpath=zeros(1,2*n); % path preallocationt=e; path(1)=t; count=1;while t=s & t0 p=pare

4、nt(t); path=p path(1:count); t=p; count=count+1;endif count=2*n error(The path preallocation length is too short.,. Please redefine path preallocation parameter.);endpath(1)=s;path=path(1:count);%算法实现clc; clear; close all;% 载入设置数据lines = load(Distance.txt);%点与点之间的距离矩阵A=lines;A(find(A10)=inf; %对步长的限制

5、，根据自己的要求决定！我们在此选择10.% A就是连接矩阵，其中对角线为0，表示本身% 有连接关系的就对应线的长度% 没有连接关系的就对应inf% 下面的是dijstra算法，有两种方式可以调用s =input(输入起点); % 起点（点的序号）e =input(输入终点); % 终点（点的序号）distance,path0 = dijkstra(A,s,e);fprintf(n Use Dijkstra the Min Distance is: %.5f n, distance);fprintf(n Use Dijkstra the Min Distance path is: n);disp(path0);A1 = A;A1(isinf(A1) = 0;d, p, pred = graphshortestpath(sparse(A1), s, e);fprintf(n Use graphshortestpath the Min Distance is: %.5f n, d);fprintf(n Use graphshortestpath the Min Distance path is: n);disp(p);for i = 1 : length(path0)