Dijkstra 's Java in Java

Question

저는 Dijkstra 's Algorithm을 사용하여 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()); 
} 

그리고 그것은 필수적인지를 당신은, 더 편리한 형태로 매트릭스을 변환 할 수 있습니다.