Dijkstra's Greedy Routing Algorithm

A routing algorithm to compute the shortest path between nodes.

Description

This time it's a well commented program for better understanding.

• MATLAB release: MATLAB 6.5 (R13)
• Other requirements: nopes

[Avinash Jain]

This code cannot do routing at all.
I input the weights, but the program did not return anything.
I do not think by just choosing the closest neighbor can do routing.
Please tell me if I am wrong.

[Bunzo Akamatsu]

Agree. This implementation is really funny! I can't see where routing is performed.
There are bunch of codes on routing on Internet. The author at least should take a look at other implementations.
http://renaud.waldura.com/doc/java/dijkstra/

[Clive Loyld]

I have tried it and it woked pretty ok, but author should have done one thing, nodes weights are taken as [A][B] etc while source and destination are taken as 1, 2, , u improve it, but still it works fine

[Tim Benhart]

It is interesting to compare the two implementations of Dijkstra routing here. I borrow some codes from the other one, and shows the route found using this code. It clearly shows that this code doesn't work.

clear;
noOfNodes = 50;
rand('state', 0);
figure(1);
clf;
hold on;
L = 1000;
R = 200; % maximum range;
netXloc = rand(1,noOfNodes)*L;
netYloc = rand(1,noOfNodes)*L;
for i = 1:noOfNodes
    plot(netXloc(i), netYloc(i), '.');
    text(netXloc(i), netYloc(i), num2str(i));
    for j = 1:noOfNodes
        distance = sqrt((netXloc(i) - netXloc(j))^2 + (netYloc(i) - netYloc(j))^2);
        if distance <= R
            matrix(i, j) = 1; % there is a link;
            line([netXloc(i) netXloc(j)], [netYloc(i) netYloc(j)], 'LineStyle', ':');
        else
            matrix(i, j) = inf;
        end;
    end;
end;

activeNodes = [];
for i = 1:noOfNodes,
    % initialize the farthest node to be itself;
    farthestPreviousHop(i) = i; % used to compute the RTS/CTS range;
    farthestNextHop(i) = i;
end;

n = noOfNodes

for p=1:n
    a(p).status=0;
end

temp=[];
acc=[];
% Taking input from user regarding source & destination nodes

s = 1
d = 15;

% converting source node to status PERMANANT
a(s).status=1;
path=s;

% if (adj(s,t)==0)
% disp('Source and Destination are Same');
% continue
% end

adj = matrix;
% Main algorithm of Greedy Dijkstra
for k=1:inf
for h=1:n
 if a(h).status==0 % If Unknown
     temp=[temp adj(s,h)];
 else
     temp=[temp inf];
 end
end
[aa,bb]=min(temp);
acc=[acc aa];
temp=[];
s=bb;
a(s).status=1;
path=[path s];
if s==d
    break
end
end

path

if length(path) ~= 0
    for i = 1:(length(path)-1)
        line([netXloc(path(i)) netXloc(path(i+1))], [netYloc(path(i)) netYloc(path(i+1))], 'Color','r','LineWidth', 0.50, 'LineStyle', '-.');
    end;
end;
hold off;
return;

[Brown Zu]

This code is so confusing. It should be titled as "Dijkstra routing". It seems that the author doesn't know what routing is, and what Dijkstra algorithm is.

[Brown Zu]

This code is so confusing. It should not be titled as "Dijkstra routing". It seems that the author doesn't know what routing is, and what Dijkstra algorithm is.

[Vann Hills]

Funny implementation!

[Milena Vasquez]

very good

[Andre Jellema]

I think Dijkstra's algorithm is implemented wrongly

[Qing Lee]

This is dijkstra algorithm?

[Sungkwan Youm]

this implementation is wrong, the code must be improved.

[Graeme Doole]

This algorithm is an incorrect formulation of the Dijkstra method.

[José Estrada Soto]

 

[Debabrata Nag]

The key concept for dijkstra algorithm is Relaxation.While the code does the initialization and selection the relaxation part is wrongly done as it requires comparison between the current value at a node and that obtained by relaxation......just simply changing the value in iterations leads nowhere........

[Abdul-Kareem A. R. Shukri Alam]

Hi;
I am Abdul-Kareem from Iraq. I have BSc in computer since and BSc in electrical engineering. Now I am student in computer engineering to get MSc degree in Information Technology engineering. My research is "Design and Implementation a Multicast Routing Algorithm for a Network".
Please I need more information about my research and the related topics. Thank you.
Best regards.
Abdul-Kareem

[adam smith]

You should improve it. It is so basic !!!
And works only for 26 node

[sweety swa]