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
