實現Dijkstra的在Java中使用算法的散列碼

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分配成本，我如何在數組中找到位置？

我在考慮使用哈希碼％array.length的，但我不知道我是否會得到碰撞（考慮到這將是隻有1字符字母）

我不是問的代碼，需要這個想法。

Answer 1

兩個想法：

1. 一個cost字段添加到您的Nodo類。這樣，您只需管理一組節點，而不是單獨的成本數組。您可以在實例化節點時分配成本，並在以後輕鬆查找它們。

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