java - 使用哈希码在 Java 中实现 Dijkstra 算法

Question

我的图表的实现是以下哈希表:

public class DiGraphHash{

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

}

其中TheList，是我自己制作的列表。

对于 Dijkstra 算法，我需要映射每个节点的成本以及到达该节点的路径。 我有以下两个数组:

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

另一个重要的细节是我的节点将是字母 A、B、C、D。

因此，当我映射节点时，例如，假设我必须为节点 A 分配成本，我如何找到数组中的位置？

我正在考虑使用 hashcode % array.length 但我不确定是否会发生冲突(考虑到它只有 1 个字符字母)

我不是在问代码，而是需要这个想法。

Answer 1

两个想法:

1. 向您的 Nodo 类添加一个 cost 字段。这样，您只需管理一组节点，而不用管理一组单独的成本。您可以在实例化节点时分配成本，并在以后轻松查找它们。

2. 比两个数组更好的数据结构可能是映射，其中键是节点本身，值是节点的成本。这是一个例子:

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