Win a copy of Escape Velocity: Better Metrics for Agile Teams this week in the Agile and Other Processes forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Frank Carver
  • Junilu Lacar
Saloon Keepers:
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • fred rosenberger

Efficiency of getting minimum of a HashSet

 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello everyone, I want to implement an Dijkstra algorithm which uses adjacency lists implemented as sets. Hence, I need to put the my Node structure into a list and I have to get the Node with the minumum distance. Currently I am using a HashSet and the min function of java collections. My question is if I would increase the efficiency with using another set type provided by the java.util package since it is not recommended to use a HashSet in order to iterate through elements, which i Í guess has to be done in order to get the Node with the minimum value distane.

Thanks in advance for an answer !
 
Saloon Keeper
Posts: 14325
321
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Instead of looking for the neighbor with the smallest distance, you should be putting all discovered nodes (neighbors of the node you're processing) into a priority queue, and then pick the next node to process by taking the first element from the priority queue. Then, all you need to do is tell the priority queue to order its elements according to their distance from the root node.

So really, what structure you use to keep track of the neighbors of each node doesn't really matter, because you'll be adding all of them to a PriorityQueue anyway. Personally I prefer to use a HashMap (node key -> node).
 
Adam Ocean
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Instead of looking for the neighbor with the smallest distance, you should be putting all discovered nodes (neighbors of the node you're processing) into a priority queue, and then pick the next node to process by taking the first element from the priority queue. Then, all you need to do is tell the priority queue to order its elements according to their distance from the root node.

So really, what structure you use to keep track of the neighbors of each node doesn't really matter, because you'll be adding all of them to a PriorityQueue anyway. Personally I prefer to use a HashMap (node key -> node).



Okay, thank you ! I did not mind using a priority queue.
 
That is a really big piece of pie for such a tiny ad:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic