# shortest path algorithm based on a recursive function

29 views (last 30 days)
feynman feynman on 11 Feb 2020
Commented: Rena Berman on 14 May 2020 at 17:10
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);

Stephen Cobeldick on 13 Feb 2020
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 on 14 May 2020 at 17:10

Steven Lord on 11 Feb 2020
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.

feynman feynman on 11 Feb 2020
yes, i did. it works so well as to be correct >90% of the time that i didn't find any problem when debugging it.
Steven Lord on 11 Feb 2020
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 on 13 Feb 2020