搜索
Dijkstra算法是寻找最短路径的一种搜索算法，由荷兰科学家提出。1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径,就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。2)算法步骤：a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则u,v正常有权值，若u不是v的出边邻接点，则u,v权值为∞。b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。d.重复步骤b和c直到所有顶点都包含在S中。算法描述：通过为每个节点保留目前为止所找到的从s到e的最短路径。为了记录最佳路径轨迹，记录路径上每个节点的前趋，通过回溯法找出最短路径轨迹。过程如下：在网上搜索一些版本的Matlab实现方法，感觉都有些毛病。经过修改，得到比较好的效果。[cpp]viewplaincopy1.function[distancepath]=Dijk(W,st,e)2.%DIJKSummaryofthisfunctiongoeshere3.%W权值矩阵st搜索的起点e搜索的终点4.n=length(W);%节点数5.D=W(st,:);6.visit=ones(1:n);visit(st)=0;7.parent=zeros(1,n);%记录每个节点的上一个节点8.9.path=[];10.11.fori=1:n-112.temp=[];13.%从起点出发，找最短距离的下一个点，每次不会重复原来的轨迹，设置visit判断节点是否访问14.forj=1:n15.ifvisit(j)16.temp=[tempD(j)];17.else18.temp=[tempinf];19.end20.21.end22.23.[value,index]=min(temp);24.25.visit(index)=0;26.27.%更新如果经过index节点，从起点到每个节点的路径长度更小，则更新，记录前趋节点，方便后面回溯循迹28.fork=1:n29.ifD(k)D(index)+W(index,k)30.D(k)=D(index)+W(index,k);31.parent(k)=index;32.end33.end34.35.36.end37.38.distance=D(e);%最短距离39.%回溯法从尾部往前寻找搜索路径40.t=e;41.whilet~=st&&t042.path=[t,path];43.p=parent(t);t=p;44.end45.path=[st,path];%最短路径46.47.48.end测试：测试用例1[cpp]viewplaincopy1.W=[050inf4025102.5001520inf253.inf1501020inf4.402010010255.25inf20100556.1025inf25550];[cpp]viewplaincopy1.[cpp]viewplaincopy1.[distance,path]=Dijk(W,1,4);distancedistance=35pathpath=164从节点1到节点4最短距离路径为1--6--4,最短距离为35测试用例2[html]viewplaincopy1.W=[01342.102inf3.32054.4inf50];[html]viewplaincopy1.[distance,path]=Dijk(W,2,4);distancedistance=5pathpath=214从节点2到节点4最短距离路径为2--1--4,最短距离为5