Raul, thank you the rosseta version works faster than every thing I tried, not to say giving correct results Danil
2018-03-05 0:12 GMT+03:00 Raul Miller <[email protected]>: > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
