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;%前驱顶点的初始化fori=1:n-1id=find(visited==0);%查找未被标号的顶点forv=idifa(u,v)+distance(u)distance(v)distance(v)=distance(u)+a(u,v);%修改标号值parent(v)=u;endendtemp=distance;temp(visited==1)=inf;%已标号点的距离换成无穷[t,u]=min(temp);%找标号值最小的顶点,返回每一列的最小值u(i)及其对应的列标t(i)visited(u)=1;%标记已经标号的顶点endmypath=[];ifparent(db)~=0%如果存在路t=db;mypath=[db];whilet~=sbp=parent(t);mypath=[pmypath];t=p;endendmydistance=distance(db);functionh=Floyd(w,MAX)%w为此图的距离矩阵%MAX是数据输入时的∞的实际值len=length(w);%Floyd算法具体实现过程fori=1:lenforj=1:lenifj==i||w(j,i)==MAXcontinue;endfork=1:lenifk==i||w(j,i)==MAXcontinue;endifw(j,i)+w(i,k)w(j,k)%Floyd算法核心代码w(j,k)=w(j,i)+w(i,k);endendendendh=w;end