I'm trying to write a program which is calculation the shortest path (A* algorithm) from A to B using OSM data as input. The program should work in Android Java. I use the data from OSM and converting it with osm_2po (is a Application which converts OSM xml files to an sql file OSM2PO) to put the data into my PostGIS database. My database has the following entries and as far as I understood it right I need the following variables from it: source_id, target_id, x1, y1, x2, y2, cost and reverse cost. Where source_id is the id of the source node based on the OSM data. (long) Where target_id is the id of the target node based on the OSM data. (long) Where x1, y1 are the coordinates of the source node (latitude and longitude). (float) Where x2, y2 are the coordinates of the target node (latitude and longitude). (float) Where cost are the generated costs from source to target. (float) Where reverse cost are the generated costs from target to source (float). In my Java program I have a data class Node, which is storing my nodes in the following structure for storing my database entries: source, target, cost, x,y, x2, y2 The data class node itself can store x1,y1, x2,y2, bool visited, sourcenode, targetnode, cost, g, h, and f. This will be stored two times. One time for src -> target and vice versa. The input has the following structure: Start Node: source = 0, target = selected start point, all other variables are set to 0. Destination Node: source = selected destination point, and all other variables are set to 0.
I have only the node where the user wants to start and nothing more. The algorithm should find out what is the next node and expand them, respectively. The pseudo code I used for implementation is from the German Wikipedia Wikipedia. The openlist is a priorityqueue and the closedlist an ArrayList. In the algorithm I use the Manhattan distance to calculate H.
My questions/problems are: Is my data structure right for such an implementation? Or do I have to use a structure which stores for a node all predecessors and successors? Do I have to set h by getting the data from my database? If yes how can I calculate h? Is it the cost of the vertices from predecessor to the next node?
If I understand correctly, each entry in the database is a graph edge - it has a source point and a destination point. I don't know what "h" represents though.
Consider renaming your Node class to "Edge" since it seems to represent the path between two nodes rather than a single node. You could use an integer for direction with the values -1, 0, 1 instead of boolean. But your data structure is fine.