Year 12s: what will be the first way you research your future options? >>

Floyds algorithm

Floydsd algorithm is applied to an n x n distance matrix. State the number of comparisons that are made with each iteration.

I don't see how to is (n-1)(n-2)

How have they worked it out x

Reply 1

DFranklin

This is a guess, as I had to look up the algorithm on Wikipedia, and I have no idea how they do this at A-level.

That said, suppose we're on the kth iteration.

Then we're looping over i, j to see if we can improve

d_{ij}

by finding routes from i->k->j. (Where

d_{ij}

is our estimate for the best path distance from i to j).

Naively, there are n choices for i, n choices for j, so n^2 comparisons.

But if i = k, i->k->j can't possibly improve

d_{ij}

(as the route is i->i->j). So we only need to consider n-1 choices for i.

Similarly, if j = i (route is i->k->i) or j = k (route is i->j->j) we can't possibly improve

d_{ij}

. So there are only n-2 choices for j we need consider.

So total number of comparisons is (n-1)(n-2).

[rant]Speaking as someone who implements algorithms for a living, in practice there would be comparisons involved in doing the looping, and comparisons involved in "skipping" the cases we've just said we can ignore. So in practice the number of comparisons would be a *lot* more than this. I find these questions more than a little silly, to be honest. [/rant]