Алгоритм Дийкстры Java Добавить на соседства

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

Есть ли способ добавить к соседям? Например:

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

В основном я хочу, чтобы проверить, если A.adjacencies имеет какое-либо преимущество, и если он добавляет вторую строку в качестве нового ребра, не переписывая первую строку.

Есть ли способ сделать это? Если этого не происходит, есть ли способ обойти эту проблему?

Answer 1

Используйте коллекцию вместо массивов. Например, ArrayLisy:

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