Code covered by the BSD License

# Breath First Search

### Anh-Dung Nguyen (view profile)

Breath First Search algorithm to find shortest paths in a network

bfs(A,s,t)
function [shortest_paths,distance] = bfs(A,s,t)
% breathe-first search algorithm as described in "Network: an Introduction
% (Newman 2010)"
% Input:
% A: adjacency matrix of the network
% s: starting node
% t: destination node
% Outputs:
% shortest_paths: all the shortest paths from s to t
% distance: vector containing distances from s to all other nodes
% Author: Anh-Dung Nguyen

distance = ones(1,size(A,1))*-1;
distance(s) = 0;
queue = zeros(1,size(A,1));
queue(1) = s;
write_pointer = 2;
sp_tree = zeros(size(A,1));
found = 0;
while read_pointer~=write_pointer % algorithm is terminated when the read and write pointers are pointing to the same element
d = distance(queue(read_pointer)); % find the distance d for the vertex in queue
for i=1:length(neighbor)
if distance(neighbor(i))==-1 % if the distance of the neighboring vertex is unknown
distance(neighbor(i)) = d+1; % assigne it distance d+1
queue(write_pointer) = neighbor(i); % store its label in the queue
write_pointer = write_pointer+1; % increase the write pointer by one
elseif distance(neighbor(i))==d+1
end
if neighbor(i)==t
found = 1;
break;
end
end
if found
break;
end
end

% reconstruction of all the shortest paths
if found
if s==t
shortest_paths = [];
else
shortest_paths = find_paths(s,t);
end
else
shortest_paths = [];
end

function p = find_paths(u,v)
if sp_tree(v,u)==1
p = v;
else
neighbors = find(sp_tree(v,:)==1);
if length(neighbors)==1
pp = find_paths(u,neighbors);
if ~iscell(pp)
p = cat(2,pp,v);
else
for m=1:length(pp)
p{m} = cat(2,pp{m},v);
end
end
else
for n=1:length(neighbors)
pp = find_paths(u,neighbors(n));
if ~iscell(pp)
p{n} = cat(2,pp,v);
else
for m=1:length(pp)
p{m+n-1} = cat(2,pp{m},v);
end
end
end
end
end
end
end