MATLAB实现Dijkstra和Floyd算法

function [mydistance,mypath]=mydijkstra(a,sb,db);

% 从起点sb到终点db通用的Dijskstra标号算法程序如下： %输入：a——邻接矩阵，a(i,j) (可以是有向值) %sb——起点的标号 db——终点的标号

%输出：mydistance——最短路的距离 mypath——最短路的路径 n=size(a,1); visited(1:n)=0;

distance(1:n)=inf; distance(sb)=0; %起点到终点的距离的初始化 visited(sb)=1; u=sb %u为最新的p标号的顶点 parent(1:n)=0; %前 驱顶点的初始化 for i=1:n-1

id=find(visited==0); %查找未被标号的顶点 for v=id

if a(u,v)+distance(u)

distance(v)=distance(u)+a(u,v); % 修改标号值 parent(v)=u; end end

temp=distance;

temp(visited==1)=inf; %已标号点的距离换成无穷

[t,u]=min(temp); %找标号值最小的顶点,返回每一列的最小值u(i)及其对应的列标t(i) visited(u)=1; %标记已经标号的顶点 end

mypath=[];

if parent(db)~=0 %如果存在路 t=db;mypath=[db]; while t~=sb

p=parent(t);

mypath=[p mypath]; t=p; end end

mydistance=distance(db);

function h=Floyd(w,MAX) %w为此图的距离矩阵

%MAX是数据输入时的∞的实际值 len=length(w);

%Floyd算法具体实现过程 for i=1:len for j=1:len

if j==i || w(j,i)==MAX continue; end

for k=1:len

if k==i || w(j,i)==MAX continue; end

if w(j,i)+w(i,k)