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 (ms) 1.3900 111.2640 316.7110 ```