AdjacencyMatrixのノード間の距離を計算する

Question

私はJavaでAdjacencyMatrixを実装しましたが、2つのノード間の距離を見つけるためにdistance（）メソッドを実装するのは苦労しています。 どのように私はそれを行うか？ 私はたくさんのことを試しましたが、私は正しい答えを得ることができないようです。

はここで距離を除く

public class AdjacencyMatrix implements Representation { 
private Node[] nodes; 
private int[][] adjacencyMatrix; 
private int numberOfNodes =0; 


public AdjacencyMatrix(File file) { 

    Scanner inFile; 
    int numNodes; 
    try { 
     inFile = new Scanner(file); 
     numNodes = Integer.parseInt(inFile.nextLine()); 

     adjacencyMatrix = new int[20][20]; 

     nodes = new Node[20]; 
     String[] line; 

     while (inFile.hasNextLine()) { 
      line = inFile.nextLine().split(":"); 
      Node from = new Node(Integer.parseInt(line[0])); 
      Node to = new Node(Integer.parseInt(line[1])); 
      int value = Integer.parseInt(line[2]); 

      if(!Arrays.asList(nodes).contains(from)) 
       addNode(from); 
      if(!Arrays.asList(nodes).contains(to)) 
       addNode(to); 


      addEdge(new Edge(from, to, value)); 

     } 


    } catch (FileNotFoundException e) { 
     System.out.print(e.getCause()); 
    } 
} 
public AdjacencyMatrix() { 

} 

@Override 
public boolean adjacent(Node x, Node y) { 
    int fromIndex = findIndex(x); 
    int toIndex = findIndex(y); 

    if(adjacencyMatrix[fromIndex][toIndex] == 1 || adjacencyMatrix[toIndex][fromIndex] ==1){ 
     return true; 
    } 
    return false; 
} 

@Override 
public List<Node> neighbors(Node x) { 
    ArrayList<Node> neighbors = new ArrayList<>(); 
    int fromIndex = findIndex(x); 
    if(x.getData().toString().equals("4")) { 
     System.out.println("FromIndex is: " + fromIndex); 
    } 

    if(x.getData().toString().equals("4")){ 
     for(int i =0; i < nodes.length; ++i){ 

      System.out.println(nodes[i] + " "); 
     } 
    } 

    for (int i = 0; i <= numberOfNodes; i++){ 
     if(adjacencyMatrix[fromIndex][i] == 1){ 

       neighbors.add(nodes[i]); 
       if(x.getData().toString().equals("4")) { 
       System.out.println("Match!: " + i); 
       System.out.println("Adding NODE: " + nodes[i]); 
      } 
     } 

    } 

    int [] nums = new int[neighbors.size()]; 
    for(int i =0; i < nums.length; ++i){ 
     nums[i] = Integer.parseInt(neighbors.get(i).getData().toString()); 
    } 
    Arrays.sort(nums); 
    ArrayList<Node> newNeighbors = new ArrayList<>(); 
    for(int i =0; i < nums.length; ++i){ 
     newNeighbors.add(new Node(nums[i])); 
    } 
    return newNeighbors; 
} 

@Override 
public boolean addNode(Node x) { 
    if(Arrays.asList(nodes).contains(x)){ 
     return false; 
    } 


    nodes[numberOfNodes] = x; 

    for (int i = 0; i <= numberOfNodes; i++){ 

     adjacencyMatrix[numberOfNodes][i] = 0; 
     adjacencyMatrix[i][numberOfNodes] = 0; 
    } 
    numberOfNodes++; 
    return true; 
} 

@Override 
public boolean removeNode(Node x) { 

    if (!Arrays.asList(nodes).contains(x)) { 
     return false; 
    } 
    for (int k = 0; k < numberOfNodes; k++) { 
     if (x.equals(nodes[k])) { 

      //decrement the number of nodes 
      numberOfNodes--; 

      for (int i = k; i < numberOfNodes; i++) { 
       nodes[i] = nodes[i + 1]; 
      } 

      for (int i = k; i < numberOfNodes; i++) { 
       for (int j = 0; j <= numberOfNodes; j++) { 
        adjacencyMatrix[i][j] = adjacencyMatrix[i + 1][j]; 
       } 
      } 

      for (int i = k; i < numberOfNodes; i++) { 
       for (int j = 0; j < numberOfNodes; j++) { 
        adjacencyMatrix[j][i] = adjacencyMatrix[j][i + 1]; 
       } 
      } 
     } 

     // 

    } 
    return true; 
} 


@Override 
public boolean addEdge(Edge x){ 

    int from = Integer.parseInt(x.getFrom().getData().toString()); 
    int to = Integer.parseInt(x.getTo().getData().toString()); 
    int fromIndex = findIndex(x.getFrom()); 
    int toIndex = findIndex(x.getTo()); 

    if(from == 4){ 
     System.out.println("Adding adjecent to 4 -> " + to); 

    } 
    if(adjacencyMatrix[fromIndex][toIndex] == 1){ 
     return false; 
    } 

    adjacencyMatrix[fromIndex][toIndex] = 1; 
    return true; 
} 

@Override 
public boolean removeEdge(Edge x) { 
    int from = Integer.parseInt(x.getFrom().getData().toString()); 
    int to = Integer.parseInt(x.getTo().getData().toString()); 
    int fromIndex = findIndex(x.getFrom()); 
    int toIndex = findIndex(x.getTo()); 

    if(adjacencyMatrix[fromIndex][toIndex] == 0 && adjacencyMatrix[toIndex][fromIndex] ==0){ 
     return false; 
    } 

    adjacencyMatrix[fromIndex][toIndex] = 0; 
    return true; 
} 

@Override 
public int distance(Node from, Node to) { 
    return 0; 
} 


@Override 
public Optional<Node> getNode(int index) { 
    return null; 
} 

@Override 
public Collection<Node> getNodes() { 

    return Arrays.asList(nodes); 
} 

public int findIndex(Node node) 
{ 
    for (int i = 0; i < numberOfNodes; ++i) 
     if (nodes[i].equals(node)) 
      return i; 
    return -1; 
}} 

すべての私の方法を働いている私の実装です（）。 正しく実装する方法がわからないので、distance（）メソッドで0を返しています。 ご協力いただければ幸いです。

Answer 1

まず、お手伝いできない場合は、私の質問に投票しないでください。

私はそれを理解しました。 は基本的に私は私のエッジを追跡するために配列を作っ：

private Edge [] edges; 

それから私は私のグラフのエッジに配列を埋め。 さて、私の距離法では、私はちょうどそれは私がこの単純な解決策について考えている必要があります:)

public int distance(Node from, Node to) { 

    for(Edge edge: edges){ 
     if(edge.getFrom().equals(from) && edge.getTo().equals(to)){ 
      return edge.getValue(); 
     } 
    } 
    return 1; 
} 

を探していた距離である値だノードへとから、ギブとのエッジを見つけ、および抽出します早く！