Implementing Dijkstra's algorithm in Java using hash code

Question

The implementation for my graph is the following hash table:

public class DiGraphHash{

private int numNodos, numArcos;
private TheList<Nodo> nodos[];
private TheList<Arco> arcos[];
private TheList<Arco> preds[];

}

where TheList, is a list I made myself.

For Dijkstra's algorithm I need to map The cost of each node and the path to reach that node. I have the following two arrays:

   int[] cost = new cost[num_nodes];
   Nodo[] path = new Nodo[num_nodes];

Another important detail, is that my nodes are going to be the letters A, B, C, D.

So when I map my nodes, for example lets say I have to assign the cost the the Node A, how do I find the position in the array?

I was thinking of using hashcode % array.length but I am not sure if I will get collisions (take into consideration that it will be only 1 char letters)

I am not asking about the code, and need the idea.

Daniel F. Thornton · Accepted Answer · 2013-02-23 04:16:30Z

1

Two ideas:

Add a cost field to your Nodo class. This way, you'll only have to manage an array of nodes, rather than a separate array of costs as well. You can assign the costs when you instantiate the nodes, and look them up easily later.
A better data structure than two arrays might be a map, where the keys are the nodes themselves and the values are the nodes' costs. Here's an example:

HashMap<Nodo, Integer> nodesToCosts = new HashMap<Nodo, Integer>();

nodes.put(nodeA, new Integer(5));
nodes.put(nodeB, new Integer(20));
nodes.put(nodeC, new Integer(10));
nodes.put(nodeD, new Integer(5));

answered Feb 23, 2013 at 4:16

Daniel F. Thornton

3,6852 gold badges30 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Alessandroempire Over a year ago

ok I like the idea! thanks. and how about this: to save the shortest "path" to each node I am going to make an array of List, where the List has Arco (Arcs in English) and this way I can use Hashcode to find the Arc of a node, and the source of that Arc is going to be the "shortest predecesor. dont know if i explained myself well.

Daniel F. Thornton Over a year ago

That sounds promising. You might also check out Java implementations from others: en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29

Collectives™ on Stack Overflow

Implementing Dijkstra's algorithm in Java using hash code

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related