sloan@uicbert.eecs.uic.edu (Bob Sloan) (05/14/91)
Just finished teaching shortest paths to my algorithms class--the O(E + V log V) version of Djikstra's algorithm using Fib. heaps to implement the priority queue. This made me wonder: What's the best known lower bound? I couldn't think of any easy transformation of sorting, so it isn't obvious to me that V log V is tight for sparse graphs. This machine, our news reader, is up and down, so I'd appreciate email directly to me at: sloan@ss1.eecs.uic.edu --Bob Sloan, U. Illinois at Chicago