Thread Subject: Logic error in simple Dijkstra code

Subject: Logic error in simple Dijkstra code

From: Ongun Palaoglu

Date: 25 Apr, 2009 05:44:01

Message: 1 of 1

NoOfNodes = 5; %ask user the number of nodes
rand();
figure(1);
clf; %clear figure
hold on;
%rand generates random numers between [0 1]. to make it >1, Multply by
%50.
xaxis = rand(1,NoOfNodes)*100;
yaxis = rand(1,NoOfNodes)*100;
plot(xaxis,yaxis,'.'); grid on; hold on;

for i = 1:NoOfNodes
    nodes{i}.x = xaxis(i);
    nodes{i}.y = yaxis(i);
    nodes{i}.visited = 0;
end
numNotVisitedNodes = NoOfNodes - 1;
nodes{1}.visited = 0;
sourcenode = nodes{1};
text(sourcenode.x,sourcenode.y, num2str('Starting Node'));
text(nodes{NoOfNodes}.x,nodes{NoOfNodes}.y, num2str('Ending Node'));
i = 1;
while (numNotVisitedNodes > 0)
    if (nodes{i}.visited == 0)
        distance(1:NoOfNodes) = 0;
        count = 1;
        for k = 1:NoOfNodes
            if (k ~= i)
                if ((nodes{k}.visited == 0) && (nodes{i}.visited == 0))
                    distance(count) = sqrt((((nodes{k}.x - nodes{i}.x)) ).^2 + (nodes{k}.y - nodes{i}.y).^2); % distances of the nodes
                end
                count = count + 1;
            end
        end
        [minDistance, nextNode] = min(distance(1:NoOfNodes-numNotVisitedNodes));
        nodes{i}.nextNode = nextNode;
        nodes{nextNode}.visited = 1;
        line([nodes{i}.x nodes{nodes{i}.nextNode}.x], [nodes{i}.y nodes{nodes{i}.nextNode}.y], 'Color','r','LineWidth',1);
        hold on;
        text(nodes{nodes{i}.nextNode}.x,nodes{nodes{i}.nextNode}.y, num2str('i+1'));
        sourcenode = nodes{nodes{i}.nextNode};
        nodes{i}.visited = 1;
        i = nextNode;
        numNotVisitedNodes = numNotVisitedNodes - 1;
    else
        i = i+1;
    end
end


Hello I wam workin on my project. there is a logic error on the
 [minDistance, nextNode] = min(distance(1:NoOfNodes-numNotVisitedNodes));

part of my code. it suppose to ignore the visited nodes. however it starts again from the very first node amd goes to second shortest node.
Can somepne help me out for this part. thank you

Tags for this Thread

Everyone's Tags:

Add a New Tag:

Separated by commas
Ex.: root locus, bode

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Tag Activity for This Thread
Tag Applied By Date/Time
dijkstra Ongun Palaoglu 25 Apr, 2009 01:45:04
rssFeed for this Thread
 

MATLAB Central Terms of Use

NOTICE: Any content you submit to MATLAB Central, including personal information, is not subject to the protections which may be afforded information collected under other sections of The MathWorks, Inc. Web site. You are entirely responsible for all content that you upload, post, e-mail, transmit or otherwise make available via MATLAB Central. The MathWorks does not control the content posted by visitors to MATLAB Central and, does not guarantee the accuracy, integrity, or quality of such content. Under no circumstances will The MathWorks be liable in any way for any content not authored by The MathWorks, or any loss or damage of any kind incurred as a result of the use of any content posted, e-mailed, transmitted or otherwise made available via MATLAB Central. Read the complete Terms prior to use.

Contact us at files@mathworks.com