dijkstrajuli_电网分区_最短距离_源码

function [sp, spcost] = dijkstra_all(matriz_costo, s, d) % This is an implementation of the dijkstra磗 algorithm, wich finds the % minimal cost path between two nodes. It磗 supoussed to solve the problem on % possitive weighted instances. % the inputs of the algorithm are: %farthestNode: the farthest node to reach for each node after performing % the routing; % n: the number of nodes in the network; % s: source node index; % d: destination node index; %For information about this algorithm visit: %http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm %This implementatios is inspired by the Xiaodong Wang's implememtation of %the dijkstra's algorithm, available at %http://www.mathworks.com/matlabcentral/fileexchange %file ID 5550 %Author: Jorge Ignacio Barrera Alviar. April/2007 n=size(matriz_costo,1); S(1:n) = 0; %s, vector, set of visited vectors dist(1:n) = inf; % it stores the shortest distance between the source node and any other node; prev = zeros(50,n); % Previous node, informs about the best previous node known to reach each network node count(1:n)=0; dist(s) = 0; while sum(S)~=n candidate=[]; for i=1:n if S(i)==0 candidate=[candidate dist(i)]; else candidate=[candidate inf]; end end [u_index u]=min(candidate); S(u)=1; for i=1:n if(dist(u)+matriz_costo(u,u)+matriz_costo(u,i))<dist(i) dist(i)=dist(u)+matriz_costo(u,u)+matriz_costo(u,i); prev(:,i)=prev(:,i).*0; prev(1,i)=u; count(i)=1; else if ((dist(u)+matriz_costo(u,u)+matriz_costo(u,i))==dist(i))&&(dist(i)~=inf)&&(u~=i) if count(i)<49 count(i)=count(i)+1; end prev(count(i),i)=u; end end end end sp=[]; stack=[]; num=[]; %建立回溯查找路径的两个栈 stack = [d,zeros(1,9)]; num=[1,zeros(1,9)]; spcost = dist(d); while stack(1) ~= 0 if stack(1)==s %记录其中一种路径 sp=[sp;stack]; %pop stack=[stack(2:10),0]; num=[num(2:10),0]; continue; end tmp=prev(num(1),stack(1)); if tmp==0 %pop stack=[stack(2:10),0]; num=[num(2:10),0]; continue; else %push num(1)=num(1)+1; stack=[tmp,stack(1:9)]; num=[1,num(1,1:9)]; end end;