Content deleted Content added
m moved Talk:Floyd-Warshall algorithm to Talk:Floyd–Warshall algorithm: WP:MOSDASH now encourages dashes in page names to match the body text |
analysis section stub expansion |
||
Line 92:
It seems like a better way to calculate the transitive closure of a graph would be to apply [[Dijkstra's algorithm]] starting at each vertex. Since you do not need the Extract-Min function at each step, since you don't care about finding the minimum path, you can do each vertex in O(e) time, or a total of O(ve). This is better than O(v^3) especially for sparse graphs. [[User:Alex319|Alex319]] 17:47, 6 June 2007 (UTC)
== Analysis Section ==
I just added: '''Therefore, the [[Computational_complexity_theory|complexity]] of the algorithm is [[big theta|<math>\Theta({n}^3)</math>]] and can be solved by a [[Deterministic Turing machine|deterministic machine]] in [[polynomial time]].''' to the analysis section. Does this need any further explanation? It feels like I would be just taking stuff from other articles if I started describing it further. [[User:Fintler|fintler]] 01:06, 11 October 2007 (UTC)
| |||