Filed under Java

Make Your Dijkstra Faster

Today I did a bit of research for GraphHopper and I stumbled over yet another minor trick which could speed up the execution of the Dijkstra algorithm. Let me shortly introduce this shortest path algorithm: If you need the path (and not only the shortest path tree) you will give the method an additional toNode … Continue reading

Failed Experiment: Memory Efficient Spatial Hashtable

The Background of my Idea The idea is to use a hash table for points (aka HashMap in Java) and try to implement neighbor searches. First of all you’ll need to understand what a spatial key is. Here you can read the details, but in short it is a binary Geohash where you avoid the memory … Continue reading

Spatial Keys – Memory Efficient Geohashes

When you are operating on geographical data you’ll use latitude and longitude to specify a location somewhere on earth. To look up some associated information or if you want to do neighborhood searches you could create R-trees, quad-trees or similar spatial data structures to make them efficient. Some people are using Geohashes instead because then … Continue reading

Free Online Graph Theory Books and Resources

A link compilation of some Hackernews and Stackoverflow posts and a longish personal investigation. The DaMN book and its companion book Graph Theory with Applications, J.A. Bondy and U.S.R. Murty Graph Theory, Reinhard Diestel Graph Theory Tutorials Digraphs: Theory, Algorithms and Applications, 1st Edition Wikipedia – Graph Algorithms Algorithms and Complexity, Herbert S. Wilf Lecture … Continue reading