Алгоритм Дейкстры в Java

Question

Я пытаюсь использовать Алгоритм Дейкстры, чтобы найти кратчайший путь в наборе вершин в Java. Я нашел код, когда люди имеют предустановленные значения, но мне не удалось найти что-нибудь с участием файлов, которые имеют матрицы для чтения в Вот код, который я в настоящее время:.

import java.util.*; 

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

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

    public static void main(String[] args) 
    { 
     // mark all the vertices 
     Vertex A = new Vertex("A"); 
     Vertex B = new Vertex("B"); 
     Vertex D = new Vertex("D"); 
     Vertex F = new Vertex("F"); 
     Vertex K = new Vertex("K"); 
     Vertex J = new Vertex("J"); 
     Vertex M = new Vertex("M"); 
     Vertex O = new Vertex("O"); 
     Vertex P = new Vertex("P"); 
     Vertex R = new Vertex("R"); 
     Vertex Z = new Vertex("Z"); 

     // set the edges and weight 
     A.adjacencies = new Edge[]{ new Edge(M, 8) }; 
     B.adjacencies = new Edge[]{ new Edge(D, 11) }; 
     D.adjacencies = new Edge[]{ new Edge(B, 11) }; 
     F.adjacencies = new Edge[]{ new Edge(K, 23) }; 
     K.adjacencies = new Edge[]{ new Edge(O, 40) }; 
     J.adjacencies = new Edge[]{ new Edge(K, 25) }; 
     M.adjacencies = new Edge[]{ new Edge(R, 8) }; 
     O.adjacencies = new Edge[]{ new Edge(K, 40) }; 
     P.adjacencies = new Edge[]{ new Edge(Z, 18) }; 
     R.adjacencies = new Edge[]{ new Edge(P, 15) }; 
     Z.adjacencies = new Edge[]{ new Edge(P, 18) }; 


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

мне нужно сделать это иметь читать в матрице любого размера в виде CSV-файла и использовать алгоритм для поиска пути.

Один из образцов файлов выглядит следующим образом:

имя

0,5,0,5,0,0,0,0,0 
5,0,5,0,8,0,0,0,0 
0,5,0,0,0,1,0,0,0 
5,0,0,0,6,0,0,0,0 
0,8,0,6,0,2,0,0,0 
0,0,1,0,2,0,0,0,6 
0,0,0,0,0,0,0,0,0 
0,0,0,0,0,0,0,0,9 
0,0,0,0,0,6,0,9,0 

Файл NineUnDirected.csv. Самый большой образец, который я должен прочитать, имеет 100 вершин.

Буду признателен за любую помощь, которую вы могли бы дать мне, чтобы прочитать в файле и запустить его через программу.

Answer 1

Scanner scanner = new Scanner(new File("NineUnDirected.csv")); 
List<Integer> matrix = new ArrayList<>(); 
while(scanner.hasNextInt()){ 
    matrix.add(scanner.nextInt()); 
} 

И тогда вы можете конвертировать матрицу в более удобной форме, если это необходимое.