When you are setting pathMatrix[i, j] = k
, you are assuming that this means that the path from node i
to j
will start by going to node k
. But in fact, what it means is that the path from i
to j
will go through k
at some point, not necessarily on the first move.
What you need to do is the following, assuming that there's a path from i
to j
:
target = j
while there is no edge from i to target:
target = pathMatrix[i, target]
This will set target
to the next node to go to from i
.