Problem 490. Fastest shortest-path-finder in the west
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.
Solution Stats
Problem Comments
-
1 Comment
The fifth test is broken; the URL specified there isn't found anymore.
Solution Comments
Show commentsProblem Recent Solvers15
Suggested Problems
-
1676 Solvers
-
68 Solvers
-
Back to basics 23 - Triangular matrix
1015 Solvers
-
323 Solvers
-
Sum of first n positive integers
588 Solvers
More from this Author38
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!