Given connectivity information about a graph, your job is to find the shortest-path distance between every pair of vertices in this graph.
Note: Valid solutions will be scored based on their speed, not their size (hence the fastest in the west...).
Format: D = mindist(from,to)
Inputs: two vectors, from and to, listing the vertex labels for each edge in the graph (note: vertex labels are positive integers, connectivity is unidirectional, meaning that a connection between vertex a and b does not imply a connection between vertex b and a; in other words this is a directed graph)
Output: D is a square matrix where D(a,b) is the number of edges in the shortest-path starting from vertex a and ending in vertex b (or inf if there is no path connecting them). Note: Your algorithm is not required to output the actual optimal paths between each pair of vertices, just their distance.
Example:
D=mindist([1,2,3],[2,3,4]) D =
0 1 2 3 Inf 0 1 2 Inf Inf 0 1 Inf Inf Inf 0
Important note & disclaimer: Your algorithm will be scored based on its speed, not based on its cody size. The reported 'size' measure for any valid entry will instead reflect the time (in milliseconds) your algorithm takes to solve various test suite problems (see the test suite for details). There has been some discussion (e.g. http://blogs.mathworks.com/desktop/2012/02/06/scoring-in-cody/#comments) regarding the cody scoring method. This problem is just a little experiment on tweaking cody to use a different scoring method other than the default node-length measure. Of course scoring based on running time has its own issues (e.g. lack of appropriate repeatability), please feel free to comment on ways you would improve how this problem is scored.
Vectorization it's much faster than "Matrixization" But I didn't expect it to be so fast!
Very interesting!! It seems though that *all* of the solutions are running now at almost an order of magnitude faster than before, rescoring all solutions now, i wonder what has changed in cody machinery, thoughts?
Scratch that, it seems cody has found a way to avoid my little hack modifying the scoring function so it is back to scoring based on code length instead of code time, i will see what i can do to fix this...
Ok, cody was friendly enough to still allow easy hacks to the scoring function (I am pretty sure they are allowing this back doors on purpose, so thanks matlab team for still permitting this sort of time-scored problems!), so this problem should be back to scoring based on time instead of length. Rescoring now...
and @fel, it seems your 'vectorized' solution outperforms my 'matrixized' solution for large and relatively dense connectivity matrices, yet it still performs a bit slower for smaller or for more sparsely connected networks...
thank you for making this kind of problems! i was a bit tired of the minimum size scoring. Good job!
After many efforts, on my PC the time for 1000 vertices and 12000 arcs is now less than 1 sec. My solution is a variant of Dijkstra's algorithm. In fact, it surprises me that all shortest paths can be found so fast. I now stop trying to improve my code. After this solution I could see the leading-time solution which is quite different. Very nice!
Dear Alfonso, thanks for doing this! Size now refers to msec's? I will now try to improve my code.
Is there a way to reproduce the new size on my PC?
Glad to help, and yes, size still refers to ms. Good luck with optimizing! (as a suggestion, try vectorizing things a bit; for example you can change the entire for loop starting with 'for w = ws,' for something like 'w=ws(isinf(D(s,ws))); D(s,w)=level; Q(tail+(1:numel(w)))=w; tail=tail+numel(w);', and that should run considerably faster)
(note, the example suggestion above refers to your latest proposed Solution 84731, not this one)
When I run test problem 5 with my code on my PC the output is
Time (ms)
1.0e+04 *
0.006900000000000 0.657700000000000 1.714100000000000
In total this is well below 20 sec. It may be not the leading time, but it is kind of frustratng that the response of Cody is that the "server encountered an error". There is no error in the code; I am sure because I compared my solutions with those obtained by using the 'graphallshortestpaths.m' routine in the Bioinformatics toolbox of Matlab. I would like to know why I get no valid response from Cody.
Sorry about that. It seems your code runs a bit slower on Cody machinery compared to your machine (~35s instead of ~17s). In any way, I modified a bit the test code to allow a larger range of times to pass under the intrinsic maximum-time imposed by the Cody machinery (now if your code runs below ~40s it will be counted as valid and scored)
Currently my code needs about 12 seconds for finding all shortest paths if the number of nodes is 1000 and the number of arcs 12000. Of course, I verified that the code is correct. But since I have no entrance to the last test problem, it is not clear why the server is not able to handle it. At least, I would be glad to be able to compare 'my' times with the leadng time.
What can to do if Cody's response to a good working Matlab program on your PC is 'Undefined function 'mindist' for input arguments of type 'double''?
This error arises because you are naming your function 'mindist_CR' instead of 'mindist' (simply change the function name and it should work just fine)
Thanks for your reply. I tried this. Now the response is: 'The server encountered an error while evaluating the solution'. Any further hint will be highly appreciated!
I get 'The server encountered an error while evaluating the solution.' Why? It runs well on my PC, giving correct solutions (at least for the first 3 test problems for which the solution is given).
Unfortunately Cody has a limit (approx. 20 seconds) on how long can a solution run before terminating it and outputting this error. You need to make your function faster in order to beat this limit (approximately, it should be able to compute the distance for a graph with 1,000 vertices and 10,000 edges in under 20 seconds; the current leading solution does this in less than a second)
I now understand. It is a pity that the Cody system does not report that the smaller problems are solved correctly. I guess the results you mention for large networks can be obtained only by commercial codes. I tried the code in the Bioinformatic toolbox. This would work, but needs a license.
Please, improve the code for testing the solutions. As I mentioned earlier the number of nodes for the test problems 2 and 4 are 9 and 99, respectively. Due to this my solutions are rejected. I am not sure what is wrong with test problem 5, but I am almost sure that also there something goes wrong.
Sorry about that, it seems there is some ambiguity as to how to interpret the 'from' and 'to' variables; test 2 has 10 nodes, not 9 (you are forgetting about node 2, which has no connections to any other node)... similarly for test 5
Thanks. I changed my code so that isolated nodes are not removed. It runs well on my PC, producing solutions identical to the 'correct' solutions, but the new code is not accepted by Cody.
373 Solvers
5570 Solvers
Project Euler: Problem 4, Palindromic numbers
102 Solvers
134 Solvers
Calculate the Number of Sign Changes in a Row Vector (No Element Is Zero)
114 Solvers