shortestpaths.java

JAVA版的蚂蚁算法(Ant Colony Optimization Algorithms)

package dk.itu.nulx30.util;

/**
 * This class is used by the path-methods to store the result of the algorithms.
 * The class contains an array of distances and an array of parent vertices.
 *
 * @author  Mikkel Bundgaard
 * @author  Troels C. Damgaard
 * @author  Federico Decara
 * @author  Jacob W. Winther
 */
public class ShortestPaths {
  /**
   * Array containing the distances from the given start vertex to all other
   * vertices.
   *
   * see dk.itu.nulx30.util.Distance
   */
  private Distance[] d;
  /** Array containing the predecessors in the solution to Dijkstras algorithm*/
  private int[] prev;

  /**
   * Accessor method for the distances in this object
   *
   * @return the distances calculated from Dijkstra
   */
  public Distance[] getDistances() {
    return d;
  }

  /**
   * Accessor method for the predecessors in this object
   *
   * @return the distances calculated from Dijkstra
   */
  public int[] getPredecessors() {
    return prev;
  }

  /**
   * Class constructor specifying the size of <code>ShortestPaths</code>.
   *
   * @param capacity the number of vertices in the graph.
   */
  public ShortestPaths( int capacity ) {
    d = new Distance[ capacity ];
    prev = new int[ capacity ];
  }

  /**
   * Method for printing out the shortest path between the the start vertex
   * and the vertex given as the argument <code>destVertex</code>.
   *
   * @param destVertex the destination vertex.
   */
  public void listPath( int destVertex ) {
    listPathPrivate( destVertex );
    System.out.print( "\n" );
  }

  /**
   * Returns the index of the next vertex on the path from <code>start</code> to
   * <code>dest</code>. If there is no path then -1 is returned. 
   *
   * @param start the start vertex
   * @param dest the destination vertex
   *
   * @return the index of the next vertex on the path or -1 if no path exists 
   */
  public int getNextVertexOnPath( int start, int dest ) {
    int tmp = dest;
    while ( prev[ tmp ] != start && prev[ tmp ] != -1 ) {
      tmp = prev[ tmp ];
    }
    if ( d[ tmp ].getDistance() == Algorithms.INFINITY ) {
      return -1;
    }
    return tmp;
  }

  /**
   * Method for printing out the shortest path between the the start vertex
   * and the vertex given as the argument <code>destVertex</code>.
   *
   * @param destVertex the destination vertex.
   */
  private void listPathPrivate( int destVertex ) {
    if ( prev[ destVertex ] != -1 ) {
      listPathPrivate( prev[ destVertex ] );
    }
    System.out.print( destVertex + " " );
  }

  /**
   * Provides a string representation of this object. The string representation
   * existing of the contents of distance/predecessor array.
   *
   * @return a string representation of this object
   */
  public String toString() {
    StringBuffer s = new StringBuffer();
    for ( int i = 0; i < d.length; i++ ) {
      s.append( i + ":(d = " + d[i] + ",prev = " + prev[i] + ")\t");
    }
    return s.toString() + "\n";
  }
}