Dijkstras Algorithmus Java Add-on-Adjacencies

Question

import java.util.PriorityQueue; 
import java.util.List; 
import java.util.ArrayList; 
import java.util.Collections; 

public class Dijkstra { 

public static void computePaths(Vertex source) { 
    source.minDistance = 0.; 
    PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>(); 
    vertexQueue.add(source); 

    while (!vertexQueue.isEmpty()) { 
     Vertex u = vertexQueue.poll(); 

     // Visit each edge exiting u 
     for (Edge e : u.adjacencies) { 
      Vertex v = e.target; 
      double weight = e.weight; 
      double distanceThroughU = u.minDistance + weight; 
      if (distanceThroughU < v.minDistance) { 
       vertexQueue.remove(v); 

       v.minDistance = distanceThroughU; 
       v.previous = u; 
       vertexQueue.add(v); 
      } 
     } 
    } 
} 

public static List<Vertex> getShortestPathTo(Vertex target) { 
    List<Vertex> path = new ArrayList<Vertex>(); 
    for (Vertex vertex = target; vertex != null; vertex = vertex.previous) { 
     path.add(vertex); 
    } 

    Collections.reverse(path); 
    return path; 
} 

    Vertex A = new Vertex("A"); 
    Vertex B = new Vertex("B"); 
    Vertex D = new Vertex("D"); 
    Vertex J = new Vertex("J"); 
    Vertex M = new Vertex("M"); 

    // set the edges and weight 
    A.adjacencies = new Edge[]{new Edge(M, 8), new Edge(D, 11)}; 
    M.adjacencies = new Edge[]{new Edge(A, 8), new Edge(J, 10)}; 
    D.adjacencies = new Edge[]{new Edge(A, 11), new Edge(J, 5)}; 
    J.adjacencies = new Edge[]{new Edge(D, 5), new Edge(M, 10)}; 

    computePaths(J); // run Dijkstra 
    System.out.println("Distance to " + A + ": " + A.minDistance); 
    List<Vertex> path = getShortestPathTo(A); 
    System.out.println("Path: " + path); 
} 
} 

class Vertex implements Comparable<Vertex> { 

public final String name; 
public Edge[] adjacencies; 
public double minDistance = Double.POSITIVE_INFINITY; 
public Vertex previous; 

public Vertex(String argName) { 
    name = argName; 
} 

public String toString() { 
    return name; 
} 

public int compareTo(Vertex other) { 
    return Double.compare(minDistance, other.minDistance); 
} 

} 

class Edge { 

public final Vertex target; 
public final double weight; 

public Edge(Vertex argTarget, double argWeight) { 
    target = argTarget; 
    weight = argWeight; 
} 
} 

Gibt es eine Möglichkeit, zu den Umgebungen hinzuzufügen? Zum Beispiel:

A.adjacencies = new Edge[]{new Edge(M, 8)}; 
A.adjacencies = new Edge[]{new Edge(D, 11)}; 

Grundsätzlich mag ich überprüfen, ob A.adjacencies jede Kante hat, und wenn es die zweite Zeile als neue Kante hinzufügt, ohne die erste Zeile zu überschreiben.

Gibt es eine Möglichkeit, es zu tun? Wenn nicht, gibt es eine Möglichkeit, dieses Problem zu umgehen?

Answer 1

Verwenden Sie eine Sammlung anstelle von Arrays. Zum Beispiel ArrayLisy:

A.adjacents = new ArrayList <Edge>(); 
A.add (new Edge (M, 8)); 
A.add (new Edge (D, 11));