[EM] Typo in "Proof that Floyd finishes in 1 pass?"
Rob Speer
rspeer at MIT.EDU
Mon Dec 22 11:36:02 PST 2003
On Mon, Dec 22, 2003 at 09:28:37AM +0000, MIKE OSSIPOFF wrote:
> I'm asking if anyone can prove that the BeatpathWinner algorithm that I
> posted a few days ago would find the strongest beatpath between each
> ordered pair of candidates _in one pass_ if the order of the indices were
> re-arranged.
You accept that the Floyd-Warshall algorithm is proven, right? I don't
have my copy of CLR around.
Floyd-Warshall shortest paths is a special case of the Floyd-Warshall
algorithm, where the path weight is calculated with + and the minimum
is taken. Floyd-Warshall can also be used for the transitive closure, or
for beatpaths, because the algorithm doesn't depend on the particular
operations that are used.
--
Rob Speer
More information about the Election-Methods
mailing list