0
我有一個有向網絡模型，由一組節點組成，每個模型迭代隨着鏈路連接在一起。爲了找到最終模型迭代中的「平均最短路徑」，我實現了Dijkstra算法，該算法計算從所有節點到所有節點的最短路徑。更具體地說，該算法計算從每個網絡3000個節點到所有其他3000個節點（如果存在路徑）的最短路徑，大約9,000,000個路徑長度，然後查找平均路徑長度。當我嘗試這種方式時，我的記憶力已經耗盡。我能夠獲得大約500個節點的平均路徑長度，其中大約250,000個路徑長度在12小時內計算。我的問題是，有什麼方法可以使代碼更有效率？或者計算多條路徑是不可行的？下面如何使我的Dijkstra算法更高效
代碼...算法本身是由Vogella http://www.vogella.com/tutorials/JavaAlgorithmsDijkstra/article.html適應
節點的聯播網，代表樹木和邊緣或鏈接代表網絡。
Dijstra算法
package network;
imports...
public class DijkstraAlgorithm {
private Context<Object> context;
private Geography<Object> geography;
private int id;
List<Tree> vertices = Tree.getVertices();
List<Nets> edges = Nets.getEdges();
private Set<Tree> settledNodes;
private Set<Tree> unSettledNodes;
private Map<Tree, Tree> predecessors;
private Map<Tree, Integer> distance;
public DijkstraAlgorithm(Graph graph) {
this.context = context;
this.geography = geography;
this.id = id;
this.vertices = vertices;
this.edges = edges;
}
setters and getters....
public void execute(Tree source){
settledNodes = new HashSet<Tree>();
unSettledNodes = new HashSet<Tree>();
distance = new HashMap<Tree, Integer>();
predecessors = new HashMap<Tree, Tree>();
distance.put(source, 0);
unSettledNodes.add(source);
while (unSettledNodes.size()>0){
Tree node = getMinimum(unSettledNodes);
settledNodes.add(node);
unSettledNodes.remove(node);
findMinimalDistances(node);
}
}
private void findMinimalDistances(Tree node){
List<Tree>adjacentNodes = getNeighbors(node);
for (Tree target: adjacentNodes){
if (getShortestDistance(target)>getShortestDistance(node)+getDistance(node,target)){
distance.put(target, getShortestDistance(node) + getDistance(node, target));
predecessors.put(target, node);
unSettledNodes.add(target);
}
}
}
private int getDistance(Tree node, Tree target){
for (Nets edge: edges){
if (edge.getStartTrees().equals(node) && edge.getEndTrees().equals(target)){
return edge.getId();
}
}
throw new RuntimeException("Should not happen");
}
private List<Tree> getNeighbors(Tree node){
List<Tree> neighbors = new ArrayList<Tree>();
for (Nets edge: edges) {
if(edge.getStartTrees().equals(node) && !isSettled(edge.getEndTrees())){
neighbors.add(edge.getEndTrees());
}
}
return neighbors;
}
private Tree getMinimum(Set<Tree>vertexes){
Tree minimum = null;
for (Tree vertex: vertexes) {
if (minimum == null){
minimum = vertex;
} else {
if (getShortestDistance(vertex)< getShortestDistance(minimum)){
minimum = vertex;
}
}
}
return minimum;
}
private boolean isSettled(Tree vertex){
return settledNodes.contains(vertex);
}
private int getShortestDistance(Tree destination) {
Integer d = distance.get(destination);
if (d == null) {
return Integer.MAX_VALUE;
} else {
return d;
}
}
public LinkedList<Tree> getPath(Tree target){
LinkedList<Tree>path = new LinkedList<Tree>();
Tree step = target;
if(predecessors.get(step)== null){
return null;
}
path.add(step);
while (predecessors.get(step)!=null){
step = predecessors.get(step);
path.add(step);
}
Collections.reverse(path);
return path;
}
}
圖
package network;
imports...
public class Graph {
private Context<Object> context;
private Geography<Object> geography;
private int id;
List<Tree> vertices = new ArrayList<>();
List<Nets> edges = new ArrayList<>();
List <Integer> intermediateNodes = new ArrayList<>();
public Graph(Context context, Geography geography, int id, List vertices, List edges) {
this.context = context;
this.geography = geography;
this.id = id;
this.vertices = vertices;
this.edges = edges;
}
setters... getters...
//updates graph
@ScheduledMethod(start =1, interval =1, priority =1)
public void countNodesAndVertices() {
this.setVertices(Tree.getVertices());
this.setEdges(Nets.getEdges());
//run Dijkstra at the 400th iteration of network development
@ScheduledMethod(start =400, priority =1)
public void Dijkstra(){
Graph graph2 = new Graph (context, geography, id, vertices, edges);
graph2.setEdges(this.getEdges());
graph2.setVertices(this.getVertices());
for(Tree t: graph2.getVertices()){
}
DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph2);
//create list of pathlengths (links, not nodes)
List <Double> pathlengths = new ArrayList<>();
//go through all nodes as starting nodes
for (int i = 0; i<vertices.size();i++){
//find the shortest path to all nodes as end nodes
for (int j = 0; j<vertices.size();j++){
if(i != j){
Tree startTree = vertices.get(i);
Tree endTree = vertices.get(j);
dijkstra.execute(vertices.get(i));
//create a list that contains the path of nodes
LinkedList<Tree> path = dijkstra.getPath(vertices.get(j));
//if the path is not null and greater than 0
if (path != null && path.size()>0){
//calculate the pathlength (-1, which is the size of the path length of links)
double listsize = path.size()-1;
//add it to the list
pathlengths.add(listsize);
}
}
}
}
calculateAvgShortestPath(pathlengths);
}
//calculate the average
public void calculateAvgShortestPath(List<Double>pathlengths){
Double sum = 0.0;
for (Double cc: pathlengths){
sum+= cc;
}
Double avgPathLength = sum/pathlengths.size();
System.out.println("The average path length is: " + avgPathLength);
}
}
內存限制只是物理上的 - 如果X> Y，則不能將X磅的東西裝入Y磅袋中。唯一的希望似乎是在多臺機器上並行化和分配計算：https：// www。 scientific.net/AMM.441.750 – duffymo
運行時最大的問題是，在每次迭代中，您都要在整個集合上搜索minimun。理想情況下，Dijkstra使用MinHeap，這是一個堆，成本最低的節點就是它的根節點。 – luizfzs
我沒有仔細閱讀代碼，但是您是否爲每對頂點運行Dijkstra算法一次？如何使用Floyd-Warshall來代替。維基百科：「算法的單次執行將找出所有頂點對之間最短路徑的長度（總和權重）。」 –