Dijkstra算法matlab实现.doc

文档介绍：Dijkstra算法matlab实现function[distance,path]=Dijkstra(a,sb,db)%输入:a--邻接矩阵;a(i,j)i到j之间的距离,可以是有向的%sb--起点的标号,db--终点的标号%输出:distance--最短路的距离;path--最短路的路径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);%找标号值最小的顶点visited(u)=1;%标记已经标号的顶点endpath=[];ifparent(db)~=0%如果存在路t=db;path=[db];whilet~=sbp=parent(t);path=[ppath];t=p;endenddistance=distance(db);end