[R] Shortest connected path in a matrix

[Suzen, Mehmet]

You may want to check bioconductor packages doing graph algorithms.
Maybe this one:
http://www.bioconductor.org/packages/release/bioc/manuals/RBGL/man/RBGL.pdf
See  for example ?dijkstra.sp

On 5 March 2014 18:44, 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.