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.

Given connectivity information about a graph, your job is to find the <http://en.wikipedia.org/wiki/Shortest_path_problem *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

152 Solutions
15 Solvers

Last Solution submitted on May 17, 2023

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Christian Schröder on 5 Mar 2023

The fifth test is broken; the URL specified there isn't found anymore.

Solution Comments

Show comments

Problem Recent Solvers15

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

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

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers15

Suggested Problems

More from this Author38

Problem Tags

Community Treasure Hunt

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

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers15

Suggested Problems

More from this Author38

Problem Tags

Community Treasure Hunt

Players