Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!caen!umich!vela!m.cs.uiuc.edu!ibma0.cs.uiuc.edu!ux1.cso.uiuc.edu!uicbert.eecs.uic.edu!sloan
From: sloan@uicbert.eecs.uic.edu (Bob Sloan)
Newsgroups: comp.theory
Subject: L. B. on shortest paths?
Message-ID: <1991May13.231928.2022@uicbert.eecs.uic.edu>
Date: 13 May 91 23:19:28 GMT
Distribution: comp
Organization: University of Illinois at Chicago
Lines: 13



	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