Cody

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

Solution 145645

Submitted on 8 Oct 2012 by Alfonso Nieto-Castanon
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, log in.

### Test Suite

Test Status Code Input and Output
1   Pass
%% % 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)

Time (ms) 0.2100

2   Pass
%% % 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)

Time (ms) 0.1940

3   Pass
%% % 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)

Time (ms) 0.2630

4   Pass
%% % 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)

Time (ms) 1.4810

5   Pass
%% % 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); fh=fopen('SetSolutionScore.p','wb'); fwrite(fh,hex2dec(reshape('7630312e30307630302e30300004301c70e71fb1000002f3000004db000007ca7153c65123117b5c4dc033eaaf23825cf9fa91752bef8d0b6bd0f3a8bd3bd6ae56474c75187aae2a5312433308ed7f8e4fa6a7e23fe9230c6dd058befa05e5429d7c6bedaaaab4797f6b9f04f5d8110502805a0e7532ea97deec840048b405249f34675a2677e3acd6db29985e8285ac335083f21c149e165e75423d323e53f6209b167eaff0ba5e3589cd3c953fb81b41596f6df3ddd711436f36e04760e1a244ce13cc7384b04d758bdca5c6d120b55ffc4598a4ecb0d1b6d76d4effa7eaef9d4347435fa126d970b6ab017baa31490782ed18f3be203262796a5eabdb681d75469e773c1fee60017c7ec5423b1d6e13c7b587ebfdfca47eb5dd7b4820c151fd8923df5ba183b076af525facc7d5121aae4ed42aabd0f4d0f38c533305f3a7f4ecb0ef95d59fa1a74b030fc27fd6b70678e2580fe41d50abf7e281d5d8cf3212d484c8e49a65596545c3813c4f28e83aad807ab1d9c1525de4bc1c1d3bc92ec5b2d93a4e27debe43ad6ba9a9b61cc3839a051fa5f44afa488a751770b100a090e967decd1e277639d9b68aed4e2ea5f225c250bd748f6c63840a7a9acb3b165f6b66ee5c4e23a86e1e7973c8fcb52881c45d49c0d614b61358b59c94c8f6c62062f5801bcb8a9f1d5c6ed94d1b66c81b1e90e6d71219056ecff29b11f378cab0ad5972787a01d2d5a2a7d88df856cbd45741b785342ebf8a3304032c09356316ae8e293651bfe52e7c8680dc5d8787f20536f2f8f0091997982e37a24123bd29e4efe6f544e25b8a84560cb1478c41218c381b950ee7ec641dd7aa9a1b887f5318155c9ec182140b186157b094350a4d2fa57accde2312046f63b6395b3acf5f33f722d2d3d25ad84d7a2dce27e86b9e38013f7646d88ba64f32d0b08a183e280c2f92d5b449631d607f16d67afd96f45f8aedc78573835c6ce5dc87f6e559f4b8ee0034d3ad1c61c2e2bdf0f8323cc6cbfa06efa23abcd19e7e0b8a8bbd6d941b06fbbb2e38e18312cb43dfd3d2ab755f1d895ba1d756786b6082d08a1b207e1bdef94f87fae04d949d2551083bbd83bbe0ce5701af0af2257ca89dde63c6af9b072216db0551a65d8732d02f7c16e7f40ff588c3394a97da68dc9ed6558ee61296d86d38c5d610e0bd9ce923c3cbc88e94c033b6284386c3d924b97f1626d74fdaf590f0d54e7a429b1065c3056ab1d8a6b063aa52727cb62626593500c1f0feb571326354b344055ea062f77342f50533ebcddda65bbe311c224eb0fec5c8759e2592d409841a219abf70240b830f44ff0d2bc2850790fcb2a68142ff71c8b0dd8f39816382d9ba9c2d10a605ecfb5610006c885013c32a9601a3da5fcc3751db480cb0236732d9ce5812da06c05165548cbefb79072e90175ebd4029a836aa839d22887ae7b6f16529ee1a167099f846355961f73f0f71178bd52ba5f19517387cc4688c7874817757edea3d4252a805177bd2bbbb45bbb2f58cae26851e31f6673949ab80c6c92ff9950c9c21133846fc27743d8d6c707f0fb0bc8ea246839fabefbc296e2f8986fe7e8432cc5cd0694793c38ade276c644101c58f18b679dd66f75f1b01312e7ad4afa674d3e6748d29d6ddbe90fdbad828dbab013555a76176f9562c8de41e16639eb5b0910adfd3dda79f93bcaf2343418b283a85c2fcf441f3bf1e7af02bbf8994eea683a54ada8dc9d01b03322e87ae1b722605b755e931104668b730af1d0e57989474420da0d167ef6adbf873db',2,[])'), 'uint8'); fclose(fh); rehash path; SetSolutionScore(round(sum(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);

Time (ms) 1.3900 111.2640 316.7110