Cody

Problem 490. Fastest shortest-path-finder in the west

Solution 76592

Submitted on 14 Apr 2012
This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.

This solution is outdated. To rescore this solution, sign in.

Test Suite

Test Status Code Input and Output
1   Pass

2   Fail
%% % test small connectivity matrix (3x3) assert(isequal(mindist([1,3,2,3],[2,2,1,2]),[0 1 Inf;1 0 Inf;2 1 0])) t0=clock; D=mindist([1,3,2,3],[2,2,1,2]); t1=etime(clock,t0)*1e3; disp('Time (ms)'); disp(t1)

Error: Undefined function 'mindist' for input arguments of type 'double'.

3   Fail
%% % test small connectivity matrix (10 vertices, 15 edges) assert(isequal(mindist([10 5 5 7 7 3 3 4 6 6 1 8 7 1 10],[7 4 10 6 8 4 1 7 9 4 6 9 6 10 9]),[0 Inf Inf 2 Inf 1 2 3 2 1;Inf 0 Inf Inf Inf Inf Inf Inf Inf Inf;1 Inf 0 1 Inf 2 2 3 3 2;Inf Inf Inf 0 Inf 2 1 2 3 Inf;Inf Inf Inf 1 0 3 2 3 2 1;Inf Inf Inf 1 Inf 0 2 3 1 Inf;Inf Inf Inf 2 Inf 1 0 1 2 Inf;Inf Inf Inf Inf Inf Inf Inf 0 1 Inf;Inf Inf Inf Inf Inf Inf Inf Inf 0 Inf;Inf Inf Inf 3 Inf 2 1 2 1 0])) t0=clock; D=mindist([10 5 5 7 7 3 3 4 6 6 1 8 7 1 10],[7 4 10 6 8 4 1 7 9 4 6 9 6 10 9]); t1=etime(clock,t0)*1e3; disp('Time (ms)'); disp(t1)

Error: Undefined function 'mindist' for input arguments of type 'double'.

4   Fail
%% % test small connectivity matrix (10 vertices, 30 edges) assert(isequal(mindist([4 10 2 9 8 2 7 10 3 7 5 9 2 6 9 3 2 9 8 7 9 9 10 8 2 7 3 2 1 8],[2 6 9 4 3 1 4 8 10 5 4 6 5 5 7 4 7 1 4 4 3 8 5 7 5 4 7 3 4 1]),[0 2 3 1 3 4 3 4 3 4;1 0 1 2 1 2 1 2 1 2;3 2 0 1 2 2 1 2 3 1;2 1 2 0 2 3 2 3 2 3;3 2 3 1 0 4 3 4 3 4;4 3 4 2 1 0 4 5 4 5;3 2 3 1 1 4 0 4 3 4;1 2 1 1 2 3 1 0 3 2;1 2 1 1 2 1 1 1 0 2;2 3 2 2 1 1 2 1 4 0])) t0=clock; D=mindist([4 10 2 9 8 2 7 10 3 7 5 9 2 6 9 3 2 9 8 7 9 9 10 8 2 7 3 2 1 8],[2 6 9 4 3 1 4 8 10 5 4 6 5 5 7 4 7 1 4 4 3 8 5 7 5 4 7 3 4 1]); t1=etime(clock,t0)*1e3; disp('Time (ms)'); disp(t1)

Error: Undefined function 'mindist' for input arguments of type 'double'.

5   Fail
%% % test medium connectivity matrix (100 vertices, 200 edges) i=[17 21 97 93 63 87 68 14 40 12 30 60 45 63 55 43 71 74 32 66 48 27 10 80 1 50 36 40 100 35 84 75 93 94 79 49 6 6 60 24 80 43 60 41 64 87 1 17 44 63 6 89 15 70 74 48 69 68 63 24 77 82 48 69 33 50 100 90 37 29 10 62 61 87 69 6 45 27 77 8 100 94 77 26 8 72 59 4 4 36 59 47 9 60 95 88 15 27 32 50 51 42 40 76 22 32 68 39 46 82 32 27 15 39 75 63 33 63 63 91 64 43 13 10 2 56 10 62 45 24 44 58 80 2 44 98 80 92 31 97 76 82 48 68 5 100 91 65 65 90 77 96 95 44 84 4 29 85 25 99 26 75 47 2 47 64 63 4 83 73 63 26 56 99 9 98 47 7 82 53 86 84 66 40 83 76 69 86 74 60 18 99 69 3 10 35 85]; j=[6 27 87 92 2 77 23 12 86 60 81 18 14 69 98 84 91 76 12 81 22 81 4 26 25 27 56 39 52 20 56 92 21 37 61 100 24 67 34 76 77 90 46 25 76 69 44 94 65 9 80 28 56 39 65 68 37 51 12 1 64 21 98 50 46 99 86 21 46 99 99 81 16 60 80 20 88 74 68 15 72 55 28 67 11 31 24 39 85 35 64 42 65 87 45 95 78 59 49 13 61 30 28 31 28 35 13 74 13 7 94 60 2 40 74 93 38 18 91 84 25 29 72 36 98 12 41 28 31 54 73 71 49 29 43 82 10 46 8 91 30 80 54 26 83 46 84 51 17 20 78 7 50 30 58 58 27 30 36 15 42 54 32 13 80 89 4 50 56 88 16 98 49 24 91 72 55 77 65 83 79 12 82 70 93 19 95 35 62 98 51 70 48 68 56 28 6]; assert(isequal(interp2(mindist(i,j),[2 55 45 33 34 87 53 43 99 50],[90 66 53 41 94 68 94 38 23 76],'nearest'),[8,5,8,Inf,7,7,Inf,Inf,Inf,9])) t0=clock; D=mindist(i,j); t1=etime(clock,t0)*1e3; disp('Time (ms)'); disp(t1)

Error: Undefined function 'mindist' for input arguments of type 'double'.

6   Fail
%% % Time-score evaluation % test medium connectivity matrix (100 vertices, 200 edges) rand('state',2); n=100;m=200; i=ceil(n*rand(1,m)); j=ceil(n*rand(1,m)); k=i==j;i(k)=[];j(k)=[]; I=ceil(n*rand(1,10));J=ceil(n*rand(1,10)); % first run for initialization assert(isequal(interp2(mindist(i,j),I,J,'nearest'),[6 6 Inf 0 5 Inf 4 8 6 3])) % second run for time evaluation t0=clock; D=mindist(i,j); t1(1)=etime(clock,t0)*1e3; % test large connectivity matrix (1000 vertices, 2000 edges) rand('state',0); n=1000;m=2000; i=ceil(n*rand(1,m)); j=ceil(n*rand(1,m)); k=i==j;i(k)=[];j(k)=[]; I=ceil(n*rand(1,10));J=ceil(n*rand(1,10)); % first run for initialization assert(isequal(interp2(mindist(i,j),I,J,'nearest'),[8 8 9 8 11 7 Inf 5 8 Inf])) % second run for time evaluation t0=clock; D=mindist(i,j); t1(2)=etime(clock,t0)*1e3; % test large connectivity matrix (1000 vertices, 10000 edges) rand('state',1); n=1000;m=10000; i=ceil(n*rand(1,m)); j=ceil(n*rand(1,m)); k=i==j;i(k)=[];j(k)=[]; I=ceil(n*rand(1,10));J=ceil(n*rand(1,10)); % second run for time evaluation t0=clock; D=mindist(i,j); t1(3)=etime(clock,t0)*1e3; assert(isequal(interp2(D,I,J,'nearest'),[3 4 3 4 4 3 3 2 3 3])) % convert time to score disp('Time (ms)'); disp(t1); feval(@evalin,'caller',sprintf('score=%d',round(sum(t1)))); %fh=fopen('mindist.m','wt'); %fprintf(fh,'%s\n',repmat('1;',[1,ceil(sum(t1)/2)])); %fclose(fh);

Error: Undefined function 'mindist' for input arguments of type 'double'.

Suggested Problems

More from this Author38

Community Treasure Hunt

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

Start Hunting!