0
私は、各モデル反復で成長するリンクによって接続されたノードのセットからなる有向ネットワークモデルを持っています。最終的なモデル反復で「平均最短経路」を見つけるために、私はすべてのノードからすべてのノードまでの最短経路を計算するDijkstraのアルゴリズムを実装しました。具体的には、アルゴリズムは、各ネットワーク3000ノードから他のすべての3000ノード（パスが存在する場合）、およそ9,000,000のパス長までの最短パスを計算し、平均パス長を求めます。私がこれを試してみると、私は記憶がなくなります。私は約500ノードまで平均パス長を得ることができます。ここでは、およそ25万パスの長さが12時間未満で計算されます。私の質問は、コードをより効率的にする方法でコードを改善する方法はありますか？あるいは、その多くの経路を計算することは実現可能ではありませんか？Dijkstraアルゴリズムをより効率的にするにはどうすればいいですか？
以下のコード...アルゴリズム自体はVogella http://www.vogella.com/tutorials/JavaAlgorithmsDijkstra/article.html neworkで
ノードから適合されている木やエッジまたはリンクがネットを表し表します。
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
実行時に起こる最大の問題は、すべての反復で、ミニマムのセット全体を検索していることです。理想的には、Dijkstra'sはMinHeapを使用します。これは最小コストのノードがそのルートにあるヒープです。 – luizfzs
私はコードをあまりよく読んでいませんでしたが、Dijkstraのアルゴリズムを頂点のペアごとに1回実行していますか？ Floyd-Warshallを代わりに使うのはどうですか？ Wikipedia： "アルゴリズムを1回実行すると、すべての頂点ペア間の最短経路の長さ（合計ウェイト）がわかります。 –