Problem 490. Fastest shortest-path-finder in the west
The fifth test is broken; the URL specified there isn't found anymore.
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
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.
Problem Recent Solvers15
Project Euler: Problem 6, Natural numbers, squares and sums.
Make a random, non-repeating vector.
Find last zero for each column
More from this Author38
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!