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

效果展示：

开头输入的是点的序列号（表示第几个点），显示的是最短路径的走法（同样以点的序列号显示，表示途径的第几个点）。

%编写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

% initialize

n=size(A,1); % node number

D=A(s,:); % distance vector path=[]; % path vector visit=ones(1,n); % node visibility

visit(s)=0; % source node is unvisible parent=zeros(1,n); % parent node

% the shortest distance

for 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: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 end end

distance=D(e);

% the shortest distance path if parent(e)==0 return; end

path=zeros(1,2*n); % path preallocation t=e; path(1)=t; count=1; while t~=s && t>0 p=parent(t);

path=[p path(1:count)]; t=p;

count=count+1; end

if count>=2*n

error(['The path preallocation length is too short.',... 'Please redefine path preallocation parameter.']);

end

path(1)=s;

path=path(1:count);

%算法实现

clc; clear; close all; %% 载入设置数据

lines = load('Distance.txt'); %点与点之间的距离矩阵 A=lines;

A(find(A>10))=inf; %对步长的限制，根据自己的要求决定！我们在此选择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) if i == length(path0)

temp = [path0(1) path0(i)]; else

temp = [path0(i) path0(i+1)]; end end

本文来源：https://www.bwwdw.com/article/zp1h.html