[Jprogramming] Shortest Path

[Eugene McDonnell]

On Mar 5, 2007, at 9:48 AM, Oleg Kobchenko wrote:

> --- June Kim <juneaftn at gmail.com> wrote:
>
>> Given an adjacent matrix of a graph, what is the simplest way in J to
>> get the shortest path(not the length[0])~ from i to j? That is, the
>> sequence of vertices that composes the shortest path in the graph,
>> which starts with i and ends with j.
>>
>> [0] the length matrix can be calculated by <./ .+~^:_
>
> With such kind of question, it's good to provide
> a short example of the adjacency matrix, sample inputs
> and desired outputs. It will save time and exclude
> misunderstanding, and increase the likelyhood that more
> people will be willing to get involved.
>
>
>

You might find my article "Jacob's Ladder" in Vector 20.4, April  
2004, useful. It's accessible online, along with other Vectors. It  
uses a scheme that is shorter than a forward search, by starting from  
both ends -- a strategy I used many many years ago.

Eugene