Cody

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.

Solve

Solution Stats

56.9% Correct | 43.1% Incorrect
Last Solution submitted on May 08, 2020

Solution Comments

Problem Recent Solvers14

Suggested Problems

More from this Author38