Label correcting algorithm for shortest path

2013 5 26
1 个回答
1 次查看（30 天）

0 个投票

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

6 个评论
显示 4更早的评论 隐藏 4更早的评论

Image Analyst
Image Analyst 2013-5-26
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
Walter Roberson 2013-5-26
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
jana 2013-5-27
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
jana 2013-5-27
Regarding the second question: Yes I still need to find the shortest path.
Walter Roberson
Walter Roberson 2013-5-27
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
jana 2013-5-28
thankyou! that was of great help.

请先登录，再进行评论。

请先登录，再回答此问题。

类别

在 帮助中心 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

产品

标签

提问:

jana
jana
2013-5-26

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by