[R] Shortest connected path in a matrix

[MacQueen, Don]

This might be done using GIS tools, where finding shortest paths between
locations is a common task. But I can't help with details.

-Don

-- 
Don MacQueen

Lawrence Livermore National Laboratory
7000 East Ave., L-627
Livermore, CA 94550
925-423-1062





On 3/5/14 9:44 AM, "McCloskey, Bryan" <bmccloskey at usgs.gov> wrote:

>Here is some example data (hopefully the monospace formatting is
>preserved):
>
>    a   b   c   d   e
>    -   -   -   -   -
>1 | F | T | F | T | F |
>    -   -   -   -   -
>2 | T | F | T | F | T |
>    -   -   -   -   -
>3 | T | T | F | F | F |
>    -   -   -   -   -
>4 | F | T | F | T | F |
>    -   -   -   -   -
>5 | F | T | F | F | T |
>    -   -   -   -   -
>
>So, for cell b1, the shortest possible path to a true value in row 5 is
>b1-a2-a3-b4-b5 (distance: sqrt(2) + 1 + sqrt(2) + 1).
>
>* Shortest paths are not necessarily unique, but I just need to find the
>length.
>
>* If it's computationally hard to guarantee the absolute shortest path, I
>can probably live with "nearly" shortest paths.
>
>* Paths can "backtrack", so the shortest path from cell e2 to row 4 is
>e2-d1-c2-b3-b4-b5.
>
>I need to calculate the shortest path for all true cells to all rows
>further down the matrix. I'm afraid I'm going to have to write some sort
>of
>recursive path-tracing algorithm, but I'm hoping there's a package already
>in existence that accomplishes this already...
>
>-bryan
>
>On Tue, Mar 4, 2014 at 1:13 PM, McCloskey, Bryan
><bmccloskey at usgs.gov>wrote:
>
>> I have a binary rectangular T/F matrix; I need to be able to calculate
>>the
>> shortest path (i.e., Pythagorean distance) between a populated cell in
>>row
>> j and any populated cell in some row j+n.
>>
>> For instance, if I have a chessboard with random black/white square
>> colors, I need the shortest distance (linear distance, not number of
>>steps)
>> for a king to get from a specified black space on the first row, to
>>_any_
>> black space in a specified further row, traveling only on black spaces.
>>
>> Any idea? Thanks,
>>
>> -bryan
>>
>
>	[[alternative HTML version deleted]]
>
>______________________________________________
>R-help at r-project.org mailing list
>https://stat.ethz.ch/mailman/listinfo/r-help
>PLEASE do read the posting guide
>http://www.R-project.org/posting-guide.html
>and provide commented, minimal, self-contained, reproducible code.