mise en œuvre de l'algorithme de Dijkstra en Java en utilisant le code de hachage

Question

La mise en œuvre pour mon graphique est la table de hachage suivante:

public class DiGraphHash{ 

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

}

où TheList, est une liste que je me suis fait.

Pour l'algorithme de Dijkstra, j'ai besoin de cartographier le coût de chaque nœud et le chemin pour atteindre ce nœud. J'ai les deux tableaux suivants:

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

Un autre détail important est que mes noeuds vont être les lettres A, B, C, D.

Alors, quand je la carte mes noeuds, par exemple disons que je dois assigner le coût au nœud A, comment puis-je trouver la position dans le tableau?

Je pensais à l'aide hashcode% array.length mais je ne sais pas si je vais obtenir des collisions (prendre en considération le fait que ce sera seulement 1 lettres char)

Je ne demande pas au sujet du code, et besoin de l'idée.

Answer 1

Deux idées:

1. Ajouter un champ cost à votre classe Nodo. De cette façon, vous n'aurez qu'à gérer un tableau de noeuds, plutôt qu'un tableau distinct de coûts. Vous pouvez affecter les coûts lorsque vous instanciez les noeuds et les rechercher plus facilement ultérieurement.

2. Une meilleure structure de données que deux tableaux peut être une carte, où les clés sont les nœuds eux-mêmes et les valeurs sont les coûts des nœuds. Voici un exemple:

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));