පහත දැක්වෙන්නේ 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;
