shortest path algorithm based on a recursive function

Question

feynman feynman 2020-2-11

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/504813-shortest-path-algorithm-based-on-a-recursive-function

评论： Rena Berman 2020-5-14

The following code is correct 90% of the time. Anybody can find the bug?

function dis=wrong(node1,nodes,node2)

% distance node 1->node 2 thru intermediate nodes (\1, 2)

global W% weight matrix

if isempty(nodes)% 1->2 directly when nodes empty

dis=W(node1,node2);return;

end

% d(1,nodes,2)=min{W(1,i)+wrong(i,nodesSub,2),i}

for ii=1:length(nodes)

i=nodes(ii);

nodesSub=nodes;nodesSub(ii)=[];% remove i from nodesSub

disTemp(ii)=wrong(i,nodesSub,node2);

disTemp(ii)=W(node1,i)+disTemp(ii);% 1->i->2

end

disTemp(ii+1)=W(node1,node2);% 1->2 directly

% optimum route

[dis,im]=min(disTemp);

2 个评论
显示无隐藏无

Stephen23 2020-2-13

Original question copied here from Google Cache:

"shortest path algorithm based on a recursive function"

The following code is correct 90% of the time. Anybody can find the bug?

function dis=wrong(node1,nodes,node2)
% distance node 1->node 2 thru intermediate nodes (\1, 2)
global W% weight matrix
if isempty(nodes)% 1->2 directly when nodes empty
    dis=W(node1,node2);return;
end
% d(1,nodes,2)=min{W(1,i)+wrong(i,nodesSub,2),i}
for ii=1:length(nodes)
    i=nodes(ii);
    nodesSub=nodes;nodesSub(ii)=[];% remove i from nodesSub
    disTemp(ii)=wrong(i,nodesSub,node2);
    disTemp(ii)=W(node1,i)+disTemp(ii);% 1->i->2
end
disTemp(ii+1)=W(node1,node2);% 1->2 directly
% optimum route
[dis,im]=min(disTemp);
											
              
            

Rena Berman 2020-5-14

(Answers Dev) Restored edit

请先登录，再进行评论。

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

Answer 1

Steven Lord 2020-2-11

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/504813-shortest-path-algorithm-based-on-a-recursive-function#answer_415003

If you have a (small, simple) test case where the answer your code gives differs from the answer you expected it to give, have you tried debugging your code on that test case using the debugging tools included in MATLAB? You can step through your code line by line and compare what the results at each step are to what the results should be.

3 个评论
显示 1更早的评论隐藏 1更早的评论

Steven Lord 2020-2-11

You asked "Anybody can find the bug?" If you've tested it thoroughly, why do you think there is a bug?

Or did you mean "Can anybody find a bug in this code?" asking for the readers of MATLAB Answers to do some manual testing on your code to determine if there's a bug in your code not where a bug is in your code?

feynman feynman 2020-2-13