MATLAB Answers

shortest path algorithm based on a recursive function

4 views (last 30 days)
feynman feynman
feynman feynman on 11 Feb 2020
Commented: Rena Berman on 14 May 2020
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 Comments

Sign in to comment.

Answers (1)

Steven Lord
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.
  3 Comments

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!

Translated by