Content deleted Content added
→Wouldn't Dijkstra's algorithm be better for transitive closure?: :Actually, for transitive closure, breadth-first search is quite sufficient. ~~~~ |
|||
Line 97:
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)
:Actually, for transitive closure, breadth-first search is quite sufficient. [[User:Dcoetzee|Dcoetzee]] 22:37, 10 June 2008 (UTC)
== Analysis Section ==
| |||