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

Created by Alfonso Nieto-Castanon

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given connectivity information about a graph, your job is to find the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Shortest_path_problem\"><w:r><w:rPr><w:b/></w:rPr><w:t>shortest-path distance</w:t></w:r></w:hyperlink><w:r><w:t> between every pair of vertices in this graph.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Note: Valid solutions will be scored based on their</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>speed</w:t></w:r><w:r><w:t>, not their</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>size</w:t></w:r><w:r><w:t> (hence the</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>fastest in the west</w:t></w:r><w:r><w:t>...).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Format:</w:t></w:r><w:r><w:t> D = mindist(from,to)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Inputs:</w:t></w:r><w:r><w:t> two vectors,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>from</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>to</w:t></w:r><w:r><w:t>, 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</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>a</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>b</w:t></w:r><w:r><w:t> does not imply a connection between vertex</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>b</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>a</w:t></w:r><w:r><w:t>; in other words this is a directed graph)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>D</w:t></w:r><w:r><w:t> is a square matrix where</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>D(a,b)</w:t></w:r><w:r><w:t> is the number of edges in the shortest-path starting from vertex</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>a</w:t></w:r><w:r><w:t> and ending in vertex</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>b</w:t></w:r><w:r><w:t> (or</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>inf</w:t></w:r><w:r><w:t> 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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ D=mindist([1,2,3],[2,3,4])\n D =\n\n 0 1 2 3\n Inf 0 1 2\n Inf Inf 0 1\n Inf Inf Inf 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Important note &amp; disclaimer:</w:t></w:r><w:r><w:t> Your algorithm will be scored based on its</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>speed</w:t></w:r><w:r><w:t>, not based on its cody</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>size</w:t></w:r><w:r><w:t>. 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.</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://blogs.mathworks.com/desktop/2012/02/06/scoring-in-cody/#comments\"><w:r><w:t>http://blogs.mathworks.com/desktop/2012/02/06/scoring-in-cody/#comments</w:t></w:r></w:hyperlink><w:r><w:t>) regarding the cody scoring method. This problem is just a little experiment on</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>tweaking</w:t></w:r><w:r><w:t> 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.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Given connectivity information about a graph, your job is to find the <a href="http://en.wikipedia.org/wiki/Shortest_path_problem">shortest-path distance</a> 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:<pre> D=mindist([1,2,3],[2,3,4])
 D =</pre><pre> 0 1 2 3
 Inf 0 1 2
 Inf Inf 0 1
 Inf Inf Inf 0</pre>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. <a href="http://blogs.mathworks.com/desktop/2012/02/06/scoring-in-cody/#comments">http://blogs.mathworks.com/desktop/2012/02/06/scoring-in-cody/#comments</a>) 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.

Solve

Solution Stats

116 Solutions
14 Solvers

Last Solution submitted on May 08, 2020

Last 200 Solutions

Solution Comments

Solution 145111

6 Comments

6 Comments

Show 3 older comments

Fel on 6 Oct 2012

Vectorization it's much faster than "Matrixization" But I didn't expect it to be so fast!

Alfonso Nieto-Castanon on 8 Oct 2012

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?

Alfonso Nieto-Castanon on 8 Oct 2012

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...

Alfonso Nieto-Castanon on 8 Oct 2012

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...

Alfonso Nieto-Castanon on 8 Oct 2012

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...

Fel on 8 Oct 2012

thank you for making this kind of problems! i was a bit tired of the minimum size scoring. Good job!

Solution 86663

1 Comment

1 Comment

Kees Roos on 8 May 2012

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!

Solution 84550

3 Comments

3 Comments

Kees Roos on 2 May 2012

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?

Alfonso Nieto-Castanon on 3 May 2012

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)

Alfonso Nieto-Castanon on 3 May 2012

(note, the example suggestion above refers to your latest proposed Solution 84731, not this one)

Solution 84030

2 Comments

2 Comments

Kees Roos on 30 Apr 2012

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.

Alfonso Nieto-Castanon on 1 May 2012

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)

Solution 81313

1 Comment

1 Comment

Kees Roos on 25 Apr 2012

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.

Solution 76592

3 Comments

3 Comments

Kees Roos on 14 Apr 2012

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''?

Alfonso Nieto-Castanon on 15 Apr 2012

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)

Kees Roos on 15 Apr 2012

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!

Solution 76528

3 Comments

3 Comments

Kees Roos on 14 Apr 2012

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).

Alfonso Nieto-Castanon on 15 Apr 2012

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)

Kees Roos on 17 Apr 2012

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.

Solution 75762

3 Comments

3 Comments

Kees Roos on 13 Apr 2012

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.

Alfonso Nieto-Castanon on 14 Apr 2012

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

Kees Roos on 14 Apr 2012

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.

Solution 74067

2 Comments

2 Comments

Kees Roos on 11 Apr 2012

Test 2 has 9 nodes (not 10); my D is 9 by 9 and correct, why does it fail your test?

Kees Roos on 11 Apr 2012

Test problem 4 has 99 nodes, not 100!

Problem Recent Solvers14

Problem Tags

distance graph shortest path speed evaluation

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

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers14

Suggested Problems

More from this Author38

Problem Tags

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

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers14

Suggested Problems

More from this Author38

Problem Tags

Players