[EM] Floyd Algorithm?
nkklrp at hotmail.com
Wed Dec 17 23:58:01 PST 2003
Either Markus or Craig Carey, I'm not quite sure which, said:
>However, Mike Ossipoff always describes the Floyd algorithm as
> > for i in range(N)
> > for j in range(N)
> > for k in range(N)
> > low=min(B[A(i,j)],B[A(j,k)]
> > if low>B[A(i,k)]
> > B[A(i,k)]=low
Wrong. I don't call that the Floyd algorithm. I don't use that piece of
code. It looks like it might be a tiny fraction of a Python strongests
beatpaths program, with at least one of its lines partly erased.
I don't guarantee that it's part of anythng that I wrote, but, if it is,
then let me explain the odd appearance of the arrays: Python, at least the
version that I was using, doesn't have multidimensional arrays. It only has
1-dimensional arrays. So I wrote a function to convert a 2-dimensional array
position to a 1-dimensional array position. I called that function "A(i,j)".
That 1-dimensional array position serves as the index variable for the
strongest beatpaths array, B[A(i,j)].
The algorithm that I'll post, however, isn't written in any particular
programming language. That will be posted within an hour or a half hour.
I do call a certain strongest beatpaths algorithm the Floyd algorithm, only
because someone on this list told us that that's what that algorithm is
I've certainly never called it a shortest paths algorithm. It's purpose is
to find the _strongest_ beatpath from each candidate to each other
candidate. The strongest beatpath from Smith to Jones could also be the
longest one. I have no idea what you're talking about when you refer to the
shortest paths algorithm. Perhaps you're talking about a different algorithm
from the strongest beatpaths algorithm.
The algorithm that I use was suggested by Steve Eppley. Apparently someone
before him had described it. I don't claim to know what its official name
It's part of the algorithm that I send people for counting BeatpathWinner.
I'll post that BeatpathWinner algorithm here in a few minutes.
Enjoy the holiday season with great tips from MSN.
More information about the Election-Methods