Label correcting algorithm for shortest path

Can any body provide a code for label correcting algorithm for shortest path. Thankyou!

[Image Analyst]

Describe what the "label correcting algorithm" is.

And do you already have the shortest path, or do you still need to find it?

[Walter Roberson]

It sort of sounds like there might be a known path but with something changed after it was calculated, and now the path needs to be "tweaked" to adjust to the new conditions. As a guess.

[jana]

Here's the label correcting algorithm. It is similar to dijiktras algorithm except that we are maintaining the node list rather than the arc list. I am not really sure how to code this algorithm especially when we also have to keep track of the LIST.

 algorithm MODIFIED LABEL CORRECTING;
begin   
  d(1) := 0 and Pred(1) := empty set ;
  d(j) := infinity  for each j in N \ {1};
  LIST := {1};
  while LIST is not empty do
    begin
      take out an element  i  from LIST;
      for each (i,j) belong to A(i)  if  d(j) > d(i) + cij then
        begin
          d(j) := d(i) + cij ;
          pred(j) := i;
          if  j doesnot belong to LIST then add  j  to  LIST;
        end;
    end;
end

[jana]

Regarding the second question: Yes I still need to find the shortest path.

[Walter Roberson]

LIST = [1];    %initialize
...
i = LIST(1);   %take out element
LIST(1) = [];
...
if ~ismember(j, LIST); LIST(end+1) = j; end   %add j if it is not there

[jana]

thankyou! that was of great help.

Answer 1

[Image Analyst]

Perhaps Steve's blog would be helpful to you: http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/