k - Shortest, Link - Disjoint paths for Matlab

Here is a useful piece of Matlab code for anyone who needs to find a set of link disjoint paths in a given undirected graph. I couldn't find a single function in Matlab to do it, so here is my solution. It is so simple and I have used the 'graphshortespath' function which is available in the Bioinformatics toolbox. Maybe not the optimal algorithm, but does the job and it was sufficient for my purpose :)

% (c)Buddhika Gunawardena , 2009
% Filename: KShortestLinkDisjointPaths.m
% Description: A simple function to calculate k shortest and link disjoint
% paths of a given undirected graph (G) from source (src) to destination
% (dst)
% Inputs:
%     G: A connectivity matrix where if (i,j) = 1, there is a link from
%        node i to node j, and 0 otherwise. Here it is always a symmetric matrix.
%     k : The number of paths to be calculated
%     src: source node
%     dst: destination node
% Outputs:
%     paths: a k x NNodes matrix that shows all k paths found. NNodes is
%     the number of nodes in the Graph. row in the matrix contain a single
%     path from source to destination. (node numbers from source until
%     destination)


function paths = KShortestLinkDisjointPaths(G,k,src,dst)

NNodes = size(G,1);

paths = zeros(k,NNodes);
for p = 1:k
[dist, path]= graphshortestpath(sparse(G), src, dst);
if (dist~=inf)
 n = size(path,2);
 paths(p,1:n)= path;
 for i = 1:n-1
     G(path(i),path(i+1))=0;
     G(path(i+1),path(i))=0;
 end
end
end

And here is an example of it's usage,

G = [ 0  1  1  0 ;
1  0  1  1 ;
1  1  0  1 ;
0  1  1  0 ];
k = 2;

src = 1;
dst = 4;

paths = KShortestLinkDisjointPaths(G,k,src,dst)

The simple graph used in this example is shown in figure above. And the output would be,

paths =

 1     2     4     0
 1     3     4     0

Cheers !

PS. I must mention the nice simple tool that I use to convert coding such that I can insert it directly in my blog. Try it yourself. Its so simple.

Dijkstra's algorithm for MatLab

යාන්ත‍ම් පො‍ඩි විවේකයක් ලැබුනා. මොනව හරි ලියන්න කියල හිත හිතා ඉන්නකොට මම ඊයෙ ලියපු Matlab code එකක් මතක් උනා.
පහත දැක්වෙන්නේ Dijkstra Algorithm එකයි. කාට හෝ මේක ප්‍රයෝජනවත් වේ යැයි මම හිතනවා. අවුරුදු ගානකට කලින් මෙම ඇල්ගොරිතම දැනන් හිටියට, මේක කොයි තරම් වෙනස් ආකාරයේ ගැටළු සදහා යොදාගත හැකිද යන්න මට වැටහුනේ මෑතකදී.

Following is an implementation of the Dijkstra's Algorithm for Matlab. This algorithm is a solution for the 'single source shortest path problem', which is useful in many applications.

This code can be pasted in a new .m file in Matlab. Then this can be used as a function.

Format of the Inputs:

src: and integer defining the source node.
ConMat: Connection Matrix, a square matrix. Each element (i,j) of the matrix defines the length of a direct link from node i to node j (if there exists a link). If there is no link from i to j, the element (i,j) must contain -1.

Output format:

The output is given in an array (and) of size N, where N is the number of nodes in the network. Each element of the output array corresponds to a Node with same index. Each element will contain the index of the node which is the closest to the corresponding node, in the shortest path to the source. The element corresponding to source node would contain -1.

Eg. If the source node is 2, and the shortest path from 2 to 7 is 2-->4-->7, then the output array would contain | x |-1| x | 2 | x | x | 4 |.
As seen, the 7th element directs us to 4 th node, which inturn directs us to node 2. Similary, the shortest path to each other node from the source node could be extracted from the output.

%An implementation of the Dijkstra's algorithm for MatLab
%(c)Buddhika Gunawardena

function ans = Dijkstra(src,ConMat)

N = size(ConMat,1);
Visited = -1*ones(N,1);  % Here -1 means Not defined
PrevNode = -1*ones(N,1);
Distance = Inf*ones(N,1);

Distance(src) = 0;
CurrentNode = src;
nVisited = 0;
while (nVisited <N)
   Visited(CurrentNode) = 1;
   for i=1:N
       if (ConMat(CurrentNode,i)>0)
           temp = ConMat(CurrentNode,i) + Distance(CurrentNode);
           if (temp< Distance(i))
               Distance(i) = temp;
               PrevNode(i) = CurrentNode;
           end
       end
   end
   minimum = 0;
   for i= 1:N        
       if (Visited(i)<0)&&(Distance(i)>0)
           if (minimum ==0)
               minimum = i;
           elseif (Distance(i)<Distance(minimum))
               minimum = i;
           end           
       end
   end
   CurrentNode = minimum;

   nVisited = nVisited +1;
end

ans = PrevNode;