You might get some ideas from https://rosettacode.org/wiki/Floyd-Warshall_algorithm#J
Good luck, -- Raul On Sun, Mar 4, 2018 at 4:09 PM, Danil Osipchuk <[email protected]> wrote: > Hi, all > > I'm toying with the Floyd–Warshall algo > http://code.jsoftware.com/wiki/Essays/Floyd trying to extend it along the > lines of https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm to > get a next-hop table > > I'm doing something wrong since what I came with is ugly in the beginning, > in the middle and in the end and I barely think it works for a simplest > cases. > I'm sure there is a better way from which I could learn something. > regards, > Danil > > > merge =: 1 : 0 NB. m is a bit mask, merge x with values of y where m is 1, > preserve shape > : > ($m)$(,m)}(x ,:&:, y) > ) > > floyd=: 3 : 0 > nh =. (($y)$#y) (y < _) merge (i."0 #~#y) NB. initialize next-hop table, > #y means unreachable > for_k. i.#y do. > m =. y > [dk =. k ({"1 +/ {) y NB. dk is distance through k, m > is a mask were it is an improvement > y =. y m merge dk NB. update the distance table > nh=. nh m merge (|: ($y)$ k{"1 nh) NB. set next-hop through k where > there is an improvement > end. > nh;y > ) > --- transcript --- > > [mx=: 3 3 $ 0 1 4 _ 0 2 _ _ 0 > 0 1 4 > _ 0 2 > _ _ 0 > > floyd mx > ┌─────┬─────┐ > │0 1 1│0 1 3│ > │3 1 2│_ 0 2│ > │3 3 2│_ _ 0│ > └─────┴─────┘ > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
