i cant get the code to give an answer. it just runs in an inf loop i believe

% dijkstra code

clc
clear
pause on
% [DIST, PATH] = dijkstrateam(source,dest)
key=('abcdefghijklmnop');
source=14
dest=1

%coord of points (x,y)
a=[132,344];
b=[159,72];
c=[296,72];
d=[296,554];
e=[159,554];
f=[384,76];
g=[567,76];
h=[567,318];
i=[524,371];
j=[524,504];
k=[388,466];
l=[589,298];
m=[508,318];
n=[488,371];
o=[388,504];
p=[384,144];  c
pos=0;
frompos=0;
load('carray.mat')
pointarray=[a;b;c;d;e;f;g;h;i;j;k;l;m;n;o;p];
disarray=zeros(16);
totarray=[1:16]
for hhh=1:16
totarray(hhh,1:16)=inf
end
satisfied=0
%set distance to array to inf
for hhh=1:16
disarray(hhh,1:16)=inf
end
%create closed list
closed=[1:16]
for hhh=1:16
closed(1,hhh)=0
end

% [0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0;1,0,1,0,1,0,0,0,0,0,0,0,1,1,1,0;0,1,0,1,0,1,0,0,1,0,1,0,1,1,1,1;0,0,1,0,1,1,0,1,0,0,1,1,1,1,1,1;1,1,0,1,0,0,0,0,0,1,0,0,0,0,1,0;0,0,1,1,0,0,1,0,0,0,0,0,0,0,0,1;0,0,1,0,0,1,0,1,1,1,0,1,0,0,0,1;0,0,0,1,0,0,1,1,1,1,1,1,1,1,0,0;0,0,1,0,0,0,1,1,0,1,0,1,1,1,0,1;0,0,0,1,1,0,1,1,1,0,0,1,0,0,1,0;0,0,1,1,0,0,0,1,0,0,0,1,1,1,1,1;0,0,0,1,0,0,1,1,1,1,0,0,0,1,0,0;0,0,1,1,0,0,0,1,1,0,1,0,0,1,0,1;0,0,1,1,0,0,0,1,1,0,1,1,1,0,0,1;0,0,1,1,1,0,0,0,0,1,1,0,0,0,0,0;0,0,1,1,0,1,0,0,1,0,1,0,1,1,1,0;];
for kk=1:16
    frompos=frompos+1;

      for k =1:16
          pos =pos+1;
          % r= array(11)
          % s=array(pos:1)
          z=(pointarray(frompos,1)-pointarray(pos,1)).^2;
          y=(pointarray(frompos,2)-pointarray(pos,2)).^2;
          x=sqrt(z+y);
          if carray(frompos,pos)==1
          disarray(frompos,pos)=x;
          end
      end

          if pos==16
             pos=0;
          end
  end

%find the amount of nodes
nodes=length(disarray);

% %open list
% open=(1:nodes-1)
% %place source in closed list
% closed(1)=source
%put all other nodes in open list
for vv =1:nodes     %CREATE OPEN ARRAY     
    open(vv)=vv
end
for go = 1:(nodes)   %PLACE ALL NONE SOURCE NODES IN OPEN AND SOURCE IN CLOSED
    if open(go)~= source
    else
        close(1)=open(go)
        open(go)=0
    end
end 

pos=source
for counter=1:nodes
 row=pos   
temparray=disarray(row,1:end)  %pull source node from distance array

%  for mmm= 1:nodes
%      if temparray(mmm)~=inf          %dont think this is needed
%          holdarray(mmm)=temparray(mmm)
%      end    

      for compcount =1:nodes              %add distances to node to current distance
          rowToNewNode= temparray(1,compcount)%distance from current node to other nodes 
          DistToRowNode=totarray(1,pos)       %distance to current node from source node

          if  totarray(1,compcount) > (rowToNewNode +DistToRowNode)         %if distance is shorter than current replace
              totarray(1,compcount)=(rowToNewNode+DistToRowNode)
          end

      end
   satisfied =0
      while satisfied == 0
            sortarray=sort(temparray)
            [rr,cc]=find(temparray==sortarray(1))  %find the closest node
            dd=find(close == cc)  %
            if cc ~= dd           %
               satisfied = 1
               close(counter) = cc     %place new node in the close list
            else
               temparray(cc)=inf       %if already in the close list change to inf and look at the next shortest distance
            if find(temparray ~= inf) == false  %if all nodes are done then stop
               break   
            end
            end
      end
  end

[Geoff Hayes]

Hi Christopher,

Where do you think that the code is getting stuck in an infinite loop? Have you put in some fprintfs to see at which points the code passes through and at which point it gets caught?

I noticed that the code has a while loop near the end which is typically the kind of loop that exhibits the infinite looping behaviour that you suggest. As the while loop conditions on satisfied==0, then if it gets set to one (as in the if condition block) then there should be no problem in exiting the while loop. I'm not sure about the else condition though...

The break (in the else body) is only called if the if condition is true i.e. find(temparray~=inf)==false. And this will be true so long as temparray has at least one element that is not inf with find returning its non-zero index (or a vector of indices) which will never be equal to false (which is zero). If temparray has all elements set to inf, then an empty matrix is returned. This is not equal to false/0 so the equality is not met and the while loop continues infinitely.

Geoff

[Image Analyst]

What happens when you step through it? See http://blogs.mathworks.com/videos/2012/07/03/debugging-in-matlab/ You'll have to debug it. That's what we'd have to do if we were to do it for you but debugging is such a crucial skill you should learn to do on your own rather than ask us. You know, teach a man to fish...

[christopher andersen]

what i have done was to put pauses and slowly work step by step to see if it is doing what i want it to do. i think it is but maybe it is a problem with what i have coded and it wont do what i am trying to do. i am not really sure is my problem or where to go next

[Geoff Hayes]

Have you been able to identify where the code is getting stuck? What is the problem to be solved by the above code?

Answer 1

[Walter Roberson]

That does not appear to be straight Dijkstra code. The reason for marking with "inf" is not obvious. It appears to me that you are perhaps trying to prevent backtracking to where you just came from, but instead you are preventing the search from ever returning to the same column even if in a different row.

Dijkstra's algorithm is usually most easily represented using matrix multiplication. When T is the transition matrix, T^n represents where you can get to in n steps. If you are looking to get from node A to node B,

Tn = T^n;
if Tn(A,B) > 0
   %there is a route that is n steps long
end

you would do this from n = 1 to n = number of nodes -- but stopping if Tn ever goes all 0.

[christopher andersen]

Pseudo-Code
Initialize CONN, c, and ng. 
Place source
 in C, g(s)=0;
Place all n ≠ ng in O and set g(n)=∞ for all n ≠ ng
Set nc= ng
While O ≠ Ø
Find all nodes n in Star(nc) using CONN
If g(nc)+c(nc,n)<g(n) and n is in O
Then g(n) =g(nc)+c(nc,n)
P(n)=nc
Set nc=n such that g(n) is minimal among n in O
Place nc in C
Remove nc from O
End loop
Determine ns
Find path from ns to ng by following P(ns) back to ng

this is the pseudo code that i was given to try to follow maybe this can help

[Walter Roberson]

what is ng ?