No. O(V^3 + V^2*log(V)) = O(V^3). So Dijkstra always is not worse than Floyd (asymptotically). In practice, one operation in Floyd's algorithm is much simpler than in Dijkstra, so if your graph is close to complete, Floyd's algorithm will be faster.
On Mon, Aug 16, 2010 at 1:32 AM, Ricardo Hahn <[email protected]>wrote: > It depends on the graph. > > If the graph is complete, E = O(V²), > then the dijkstra would become O(V³ + V (V²) lg V ), that is worse than > Floyd Warshall > > > On Sun, Aug 15, 2010 at 6:26 PM, Mohamed Ghoneim <[email protected]>wrote: > >> Dear all, >> I have a question concerning Dijkstra and Floyd Warshall, which way >> is better to get all pair shortest path, is it through using dijkstra and >> looping through all the verticies and using them to find the shortest path >> to any other point O(E * V + V^2 * log(V)) , or just to execute floyed >> warshall on the graph O(V^3) >> >> Thanks >> Mohamed Sayed Ghoneim >> >> -- >> You received this message because you are subscribed to the Google Groups >> "google-codejam" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<google-code%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/google-code?hl=en. >> > > > > -- > []'s, > Ricardo > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<google-code%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > -- Best regards, Дектярев Михаил -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
