Re: [boost] BGL: dijkstra questions

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-15 20:00:58

----- Original Message -----
From: "Lie-Quan Lee" <llee_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Tuesday, January 15, 2002 5:30 PM
Subject: Re: [boost] BGL: dijkstra questions

> On Tue, 2002-01-15 at 17:12, David Abrahams wrote:
> >
> > ----- Original Message -----
> > From: "Jeremy Siek" <jsiek_at_[hidden]>
> >
> > >
> > > The only down-side I can see for this algorithm is that the queue can
get
> > > a little bigger due to the same vertex showing up multiple times.
However,
> > > since the queue insert/remove is logarithmic, I doubt that would have
a
> > > significant effect. It will be interesting to compare execution times.
> >
> > In your dijkstra, the same target vertex appears only once in the queue?
> > Hmm, note that the queue must be made |E| big in my case. Still, you
need a
> > queue anyway. I guess data movement could be expensive. If you had a
queue
> > with a hash table you could easily modify my algorithm to do the same
thing:
> >
> > Q is a priority queue of triples (u,v,x)
> > It has an associated hash table indexed on v so that when you do
INSERT(q,
> > (u,v,x)):
> >
> >     if (t,v,x') is in the queue for some t,x'
> >         if x < x'
> >             (t,v,x') is replaced with (u,v,x)
> >     else
> >         (u,v,x) is inserted
> >
> > Wow, seems kinda complicated. I bet it's hard to win with this method.
> > Complicated code has a way of slowing things down ;-)
>
> I guess that you have come back to the DECREASE-KEY operation now.

I never really understood its purpose or what it did until Jeremy mentioned
that there was less in the queue. I've said it before: the documentation
could be clearer. Anyway, I wouldn't say I've come back to it, but I can see
why some programs would benefit.

I'd guess it could be important in large, heavily connected graphs. Is it a
clear win for every problem? DECREASE-KEY is still a log(N) operation just
like regular insertion into a priority queue. You are banking that all paths
to a vertex are close enough in cost that they won't move very far in the
queue, right?