# WDM Network Blocking Computation Toolbox

### Przemyslaw Pawelczak (view profile)

21 Apr 2004 (Updated )

Blocking computation in WDM Networks for three different types of constraints.

varargout=shortest_path_dijkstra_all(varargin)
```function varargout=shortest_path_dijkstra_all(varargin)
%SHORTEST_PATH_DIJKSTRA_ALL Compute all shortest paths between two edges in
%a directed/undirected graph with wages.
%   PATH=SHORTEST_PATH_DIJKSTRA_ALL(BEGIN,END,NAME,STRUC_DIM) uses modified
%   Dijkstra's algorithm [1] for computing all shortest paths between BEGIN
%   and END node for a NAME.mat network (ie. help CREATE_NETWORK).
%   STRUC_DIM is the structure number saved in NAME.mat file.
%
%   Because it is possible, that graph has more than one path between two
%   nodes with the shortest length this function computes all such paths.
%
%   Dijkstra's algorithm computes only one shortest path choosen randomly
%   among all possible paths (depending how the incidence nodes were
%   given). In this function Dijkstra's algorithm has been modified to
%   manage the task. For details - in MATLAB print EDIT
%   SHORTEST_PATH_DIJKSTRA_ALL.
%
%   CREATE_NETWORK, CREATE_RAND_NETWORK.
%
%   References:
%      [1]  T. E. Cormen et al., "Introduction to Algorithms",
%      WNT, Warsaw 2000, page 593.

%   E-mail: przemyslaw_pawelczak@idg.com.pl
%   Wroclaw University of Technology, Poland
%   \$Revision: 1.0 \$  \$Date: 2004/02/12 17:49:21 \$

%If no NUMBER specified then it will be first
if nargin==3
varargin{4}=1;
end

%Exeption handling
message=nargchk(3,4,nargin);
testing_int=[varargin{1},varargin{2},varargin{4}];
if ~isempty(message)
error('MATLAB:SHORTEST_PATH_DIJKSTRA_ALL:NumberOfInputArguments',...
message);
end
if find(isnan(testing_int))
error('MATLAB:SHORTEST_PATH_DIJKSTRA_ALL:ArgumentType',...
'Arguments must be numbers.');
end
%Check if VARARGIN are positive integers
if sum([testing_int<0,fix(testing_int)~=testing_int])~=0
error('MATLAB:SHORTEST_PATH_DIJKSTRA_ALL:ArgumentType',...
'Arguments must be positive integers.');
end
if ~isstr(varargin{3})
error('MATLAB:SHORTEST_PATH_DIJKSTRA_ALL:ArgumentType',...
'Argument must be string.');
end

%Change string into number (for all number arguments)
for k=[1,2,4]
if isstr(varargin{k})==1
varargin{k}=str2num(varargin{k});
end
end

%List all '*.mat' files in current working directory
%Change directory to MATLABROOT\networks - catalog must exist
cd([matlabroot,['\work\networks']]);
directory=what;
directory=struct2cell(directory);
directory=cellstr(directory{3});

%Check if specified '*.mat' file already exist
if find(strcmp(directory,[varargin{3},'.mat'])==1)
fields_vector=[exist('description'),exist('structure')];
if length(find(fields_vector))~=2
else
varargout{1}=dijkstra_all(varargin{1},varargin{2},structure,varargin{4});
end
else
end

%Check how many nodes are in the graph
structure_dimension=cellfun('ndims',structure);
structure_length=length(structure_dimension(:,1,1));
node_number=0;
for k=1:structure_length
if ~isempty(structure{k,1,number})
node_number=node_number+1;
end
end

%Modified Dijkstra's algorithm

%Initialize variables
distance(1:node_number)=Inf;
previous=zeros(1,node_number);
queue(1:node_number)=1:node_number;
S=[];

distance(begin_node)=0;
checker(begin_node)=0;

%Because in this modification distances and previos nodes vectors might be
%different for every end node, they must be initialized separately
for k=1:node_number
Distance{1,k}=distance;
Previous{1,k}=previous;
end

while length(S)~=node_number

%Extract min
places=find(queue==Inf);
distance_temp=distance;
distance_temp(places)=NaN;
%function MIN chooses all min elements in vector
position=find(distance_temp==min(distance_temp));
%Assign smallest element to NODE
node=queue(position(1));
%Add new element to S - vector of computed nodes
S=[S,node];
%Remove from queue (replace it by Inf)
queue(position(1))=inf;

node_incidence_vector=structure{node,1,number};
wages_vector=structure{node,2,number};

for k=1:length(node_incidence_vector)
current_distance=Distance{r,node};
current_previous=Previous{r,node};
%Relaxation
if distance(node_incidence_vector(k))>current_distance(node)+wages_vector(k)
distance(node_incidence_vector(k))=current_distance(node)+wages_vector(k);
previous(node_incidence_vector(k))=node;
%If there are distances shorter than previous ones - update
Distance{1,node_incidence_vector(k)}=distance;
Previous{1,node_incidence_vector(k)}=previous;
%And remove all the other distances
for m=2:size(Previous,1)
%SIZE function is used against STRUCT_SIZE because now we
%can add as many empty vectors as long is the structure,
%not just as long is the stucture on
%node_incidence_vector(k) position
Distance{m,node_incidence_vector(k)}=[];
Previous{m,node_incidence_vector(k)}=[];
end
elseif distance(node_incidence_vector(k))==current_distance(node)+wages_vector(k)
%Update PREVIOUS vector
current_previous(node_incidence_vector(k))=node;
%Count how many vectors are in the struct
%Update them
end
end
end
end

%Show all paths
for k=1:struct_size(Previous,end_node)
position=end_node;
previous=Previous{k,end_node};
while position~=begin_node
position=previous(position);
end
%Store all paths in a matrix