Re: Missing feature in p_queue

Article View: comp.lang.c++.leda

Article #63

Back to comp.lang.c++.leda Previous Next

#63

From: David F. Skoll
Date: Fri, 01 Sep 1995 18:51

25 lines
1429 bytes

In article <BMC4BCOG@inka.de>, Muzzulini Frank
(hb04@rz70.rz.uni-karlsruhe.de) wrote:

> I had to implement a shortest path algorithm and since I didn't use
> LEDA-Graphs and nodes, I tried to implement Dijkstra's Algorithm with
> a normal p_queue. But then I found, that given a specific information
> which must be in the queue, I can't find the associated pq_item and
> without that, I can't decrease the priority or delete the information
> out of the queue.

> It seems to me, there should be a member

> 	pq_item Q.find(I i)

> in class p_queue, or have I missed something?

You can't implement Q.find efficiently.  I modified my classes to hold
an instance of pq_item, which I set when I stuff them in the priority
queue.  This only works, of course, if your objects can only be on
on priority queue at a time.

--
David F. Skoll
<a HREF="http://www.doe.carleton.ca/students/dfs/">
Click here for my home page</a> "Query two pi" on typewriter.

Technical Details

Message-ID: <DE8pq5.4pC@cunews.carleton.ca>

Path: arc1-ca.pugleaf.net!howland.reston.ans.net!torn!nott!cunews!dfs

References: <BMC4BCOG@inka.de>

Show Full Headers

Complete Article Headers

Newsgroups: comp.lang.c++.leda
Path: arc1-ca.pugleaf.net!howland.reston.ans.net!torn!nott!cunews!dfs
From: dfs@doe.carleton.ca (David F. Skoll)
Subject: Re: Missing feature in p_queue
X-Nntp-Posting-Host: sisko.doe.carleton.ca
Message-ID: <DE8pq5.4pC@cunews.carleton.ca>
Sender: news@cunews.carleton.ca (News Administrator)
Organization: Carleton University
X-Newsreader: TIN [version 1.2 PL2]
References: <BMC4BCOG@inka.de>
Date: Fri, 1 Sep 1995 18:51:41 GMT

Reply to Parent Message