Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Priority Queues I

java shortest path

  • Please log in to reply
6 replies to this topic

#1 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3038 posts
  • Programming Language:Java, C#, PHP, JavaScript, Ruby, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Ruby, Transact-SQL, Assembly, Scheme, Haskell, Others

Posted 11 November 2009 - 04:59 PM

Priority Queues

A priority queue is similar to a Queue. Items are removed from the queue in a certain order. In a queue the order is FIFO (meaning first-in, first-out). The first item added to the queue is the first item to be removed from the queue.

A priority queue removes items in an order defined by a comparator. A comparator is an object that defines how objects should be ordered. You might have seen this is if you have looked at sorting objects.

Let us look at this compare to method:

public int compareTo(Golfer g) {
        if (g.nScore > nScore) {
            return -1;
        }

        if (g.nScore < nScore) {
            return 1;
        }

        return -g.sName.compareTo(sName);
    }

If we had objects in a priority queue that had this compareTo method, the next item removed would be the one with the lowest score. However, if the scores are equal, then the player in alphabetical order will be returned.

This is a nice way to do some sorting without actually calling Arrays.sort or Collections.sort.

Creating a Priority Queue

A priority queue is a generic class that can only hold objects. It is created like this:

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

Adding to a Priority Queue

Adding an item is as simple as calling the .add method of the PriorityQueue class.

pq.add(5);
pq.add(4);
pq.add(8);
pq.add(12);
pq.add(1);
pq.add(-1);

Removing Items

We simply call the remove method and the next item is removed. The next item is determined by the comparator.

Try this code:

 while (!pq.isEmpty()) {
      System.out.println(pq.remove());
 }

The output is:

-1
1
4
5
8
12


Noticed, how it is sorted? This makes for a really great way to do some sorting.

Other uses?

Another use for this class is in implementing Dijkstra's Single Pair Shortest Path Algorithm. This is something I will discribe later. Basically Dijkstra's Algorithm allows us to find the shortest path between any two nodes. We would use a priority queue to choose the next node that is a shortest distance from the starting node.

It is called the Single Pair Shortest Path Algorithm because it finds all the shortest paths from a start node to all other nodes.

Dijkstra's Algorithm is just one use of this algorithm.
  • 4

#2 Guest_Jordan_*

Guest_Jordan_*
  • Guest

Posted 12 November 2009 - 06:09 AM

Well written, +rep!
  • 0

#3 BlaineSch

BlaineSch

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1559 posts

Posted 12 November 2009 - 08:38 AM

Wonderful + Rep!
  • 0

#4 ThemePark

ThemePark

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 147 posts

Posted 12 November 2009 - 12:31 PM

Cool, didn't know about priority queues or that Java had them. +rep

So the Djikstra algorithm you mention, can be used for approximating a solution to the TSP problem, right? If so, I'd love to see an article on that.

Edit:
Okay, so I have to spread some rep before I can give you any. Once I can +rep you again, I will.
  • 0

#5 debtboy

debtboy

    CC Devotee

  • Just Joined
  • PipPipPipPipPipPip
  • 499 posts

Posted 12 November 2009 - 01:24 PM

Good Tutorial +rep :)
  • 0

#6 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3038 posts
  • Programming Language:Java, C#, PHP, JavaScript, Ruby, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Ruby, Transact-SQL, Assembly, Scheme, Haskell, Others

Posted 12 November 2009 - 05:26 PM

Cool, didn't know about priority queues or that Java had them. +rep

So the Djikstra algorithm you mention, can be used for approximating a solution to the TSP problem, right? If so, I'd love to see an article on that.

Edit:
Okay, so I have to spread some rep before I can give you any. Once I can +rep you again, I will.


Thanks. I believe it can, I haven't looked at the TSP problem very much but doesn't it just come down to finding the shortest path from a city to some other city? http://nayuki.eigens...ite200601p5.pdf

So yes, you can use Dijkstra's algorithm to get a solution for this problem. :) I'll do a write up later. :D
  • 0

#7 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 13 November 2009 - 08:31 AM

Nice job. +rep
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/






Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download