Implementing Dijkstra’s algorithm in Java

Tags: , ,



I’ve done a fair bit of reading around this, and know that discussions regarding this algorithm in Java have been semi-frequent. My issue with implementing Dijkstra’s algorithm in Java is simply that I’m not sure how to prepare my data.

I have a set of coordinates within an array, and a set of 1s and 0s in a matrix that represent whether there is a path between the points that the coordinates represent. My question is, how do I present this information so that I can search for the best path with Dijkstra? I have seen many people create a “Node” class, but they never seem to store the coordinates within that Node. Is there some standardized way of creating this kind of structure (I suppose it’s a graph?) that I am simply missing?

Any help would be appreciated.

Answer

There are two main options:
1. You can use an adjacency matrix in which rows an columns represent your nodes. The value matrix[x, y] must be the weight(e.g. distance/cost etc.) to travel from x to y. You could use the Euclidian distance to calculate these values from your coordinate array;
2. You can implement a couple of classes (Node, Edge – or just Node with a internal Map to another node and the weight as a map value) – it is a graph indeed.



Source: stackoverflow