Talk:Floyd-Warshall's Algorithm

From Algorithmist
Jump to navigation Jump to search

Three comments. 1. I don't think it requires triangle inequality.. I haven't deleted it, I just commented it out, let me know if I'm wrong.. 2. It's just a simple dynamic programming.. but maybe we should change the pseudo-code to the O( n^3 ) space version to show to beginners the recurrence.. 3. Writing out the recurrence (or psuedocode in its recursive form) should illustrate better what we're doing.. instead of giving them a black box of "three for loops" (which admittingly, got by for me for quite some time..) Larry 12:59, 9 Dec 2005 (EST)

You're right about 1. (The triangle inequality was already there in the original article, though; I only gave it a name). We aren't really "using" the triangle inequality. About 2 (and 3), the dilemma is more general—should the easier-to-understand version be presented, or the more efficient one? What is important for Algorithmist—explaining algorithms or just giving the best possible ones? Aboyner 20:42, 9 Dec 2005 (EST)
I think that in cases like this one the best way is to present both approaches. Start with the simple & pedagogical one. Once everything is clear, show the practical one and explain why it does the same. --Misof 18:48, 11 Dec 2005 (EST)

Also, don't forget to add a pre-condition about negative cycles in the graph... and a paragraph about their detection. --Misof 18:50, 11 Dec 2005 (EST)

Isn't it weird that the psuedo code is takes up O(n^3) space while you said that floyd warshall uses O(n^2). Personally I think the O(n^3) space is really waste of memory. Better to do the normal O(n^2) space floyd warshall.--Roticv 14:25, 31 Dec 2005 (EST)

I wanted to make the dynamic programming part (the recurrence) clear to a newcomer. Probably a better wording/integration would help! --Larry 16:06, 31 Dec 2005 (EST)

What's wrong with the "code" tags? Why does the first line come outside the box? "pre" is too primitive to use; code would be better if it worked... --Aboyner 01:15, 1 Jan 2006 (EST)

Nevermind, we don't need code tags at all. An offset by a few spaces before every line does the job. --Aboyner 01:20, 1 Jan 2006 (EST)
I would prefer to keep the tags explicit rather than implicit, as it is consistent with the rest of the site, and more control over what is outputted. The O(n^3) was made to be explicit (and intentionally so), and it doesn't really make sense to have one dimension in subscript while the others are not.. we can write about how to reduce the space to O(n^2).. --Larry 14:12, 2 Jan 2006 (EST)
Firstly, I had misunderstood the purpose of the code tags. It looks like they don't put stuff in a box, they don't do anything beyond what the tt tags do—the box effect was because the rest of the lines were all indented :) I think the pre tags are too restrictive, it does not allow any HTML or other markup, or highlighting... it's like plaintext. Using leading spaces is more expressive, and it gives as much control as pre (I think. Look at ). pre, unlike code, does not carry any semantic meaning attached to it, so I don't see why explicit tags are better. As for being consistent with the rest of the site, I think we should first decide which is better and then use it for the rest of the site, and not be constrained by choices made in the past (those can be changed, anyway). And FWIW, Wikipedia uses leading spaces for code samples, at least on those pages I checked.
You are right that it looks odd to have one dimension in the subscripts and two others not, sorry about that... cool ideas aren't, especially those that occur at midnight :) --Aboyner 23:55, 2 Jan 2006 (EST)