图的表示和最短路径问题

Question

各位大哥，小弟新学java未久，奈何这次的课题与图论有关，对使用collection实在有点琢磨不透，主要问题是有一有向图， 用Dijkstra 方法求最短路径。 我建了结点类和边类， 但是图的几个关键方法不知道怎么做。 希望能得到大家的指点：）
/**
 * Representation of a graph vertex
 */
public class Vertex {
private final String label;   // label attached to this vertex /**
 * Construct a new vertex
 * @param label the label attached to this vertex
 */
public Vertex(String label) {
if(label == null)
throw new IllegalArgumentException("null");
this.label = label;
} /**
 * Get a vertex label
 * @return the label attached to this vertex
 */
public String getLabel() {
return label;
}

/**
 * A string representation of this object
 * @return the label attached to this vertex
 */
public String toString() {
return label;
} //auto-generated: hashes on label
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((label == null) ? 0 : label.hashCode());
return result;
} //auto-generated: compares labels
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final Vertex other = (Vertex) obj;
if (label == null) {
if (other.label != null)
return false;
} else if (!label.equals(other.label))
return false;
return true;
}
}
/**
 * Representation of a directed graph edge.
 */
public class Edge {
public final Vertex from,to;
public final int w; /**
 * Construct a new edge
 * @param from start vertex
 * @param to end vertex
 * @param w weight of this edge
 */
public Edge(Vertex from, Vertex to, int w) {
if(from == null || to == null)
throw new IllegalArgumentException("null");
this.from = from;
this.to = to;
this.w = w;
} /**
 * A string representation of this object
 * @return A string of the form <from, to, weight>
 */
public String toString() {
return "<"+from+", "+to+", "+w+">";
} //auto-generated: hashes on all fields
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((from == null) ? 0 : from.hashCode());
result = prime * result + ((to == null) ? 0 : to.hashCode());
result = prime * result + w;
return result;
} //auto-generated: compares all fields
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final Edge other = (Edge) obj;
if (from == null) {
if (other.from != null)
return false;
} else if (!from.equals(other.from))
return false;
if (to == null) {
if (other.to != null)
return false;
} else if (!to.equals(other.to))
return false;
if (w != other.w)
return false;
return true;
}
}
但是graph.java的几个关键方法不知道该怎么写：import java.util.*;/**
 * A representation of a graph.
 * Assumes that we do not have negative cost edges in the graph.
 */
public class MyGraph implements Graph {
private Collection<Vertex> myVertices; //the vertices in this graph
private Collection<Edge> myEdges; //the edges in this graph /**
 * Creates a MyGraph object with the given collection of vertices
 * and the given collection of edges.
 * @param v a collection of the vertices in this graph
 * @param e a collection of the edges in this graph
 */
public MyGraph(Collection<Vertex> v, Collection<Edge> e) {     ？？ }
/** 
 * Return the collection of vertices of this graph
 * @return the vertices as a collection (which is anything iterable)
 */
public Collection<Vertex> vertices() {     ？？ } /**
 * Return the collection of edges of this graph
 * @return the edges as a collection
 */
public Collection<Edge> edges() {    ？？ } /**
 * Return a collection of vertices adjacent to a given vertex v. 用邻接表表示
 *   i.e., the set of all vertices w where edges v -> w exist in the graph.
 * @param v one of the vertices in the graph
 * @return an iterable collection of vertices adjacent to v in the graph
 */
public Collection<Vertex> adjacentVertices(Vertex a) {     ？？ } /**
 * Test whether vertex b is adjacent to vertex a (i.e. a -> b) in a directed graph.
 * @param a one vertex
 * @param b another vertex
 * @return cost of edge if there is a directed edge from a to b in the graph 
 * Return -1 otherwise.
 * (Including returning -1 if one of the two vertices does not exist.)
 * Assumes that we do not have negative cost edges in the graph.
 */
public int isAdjacent(Vertex a, Vertex b) {     ？？ } /**
 * Returns the shortest path from a to b in the graph.  Assumes positive
 * edge weights.
 * @param a the starting vertex
 * @param b the destination vertex
 * @param path a list in which the path will be stored, in order, the first
 * being the start vertex and the last being the destination vertex.  the
 * list will be empty if no such path exists.  NOTE: the list will be
 * cleared of any previous data.
 * @return the length of the shortest path from a to b, -1 if no such path
 * exists.
 */
public int shortestPath(Vertex a, Vertex b, List<Vertex> path) {     ？？ }}非常感谢！！

Answer 1

楼主解决了吗？以前遇到的时候我这还保存了一段代码。希望对你有帮助吧。import java.util.*;public class BBShortest
{
 static class HeapNode implements Comparable//最小堆结点表示
 {
  int i;   // vertex number
  float length;// current length
  HeapNode(int ii, float ll)
  {
   i = ii;
   length = ll;
  }
  public int compareTo(Object x)
  {
   float xl = ((HeapNode)x).length;
   if (length < xl) return -1;
   if (length == xl) return 0;
   return 1;
  }
 }
 
 public static void shortest(int v, float []dist, int []p ,int [][] a)
 {//求最短路径
  int n = p.length-1;
  BinaryHeap heap = new BinaryHeap();
  HeapNode enode = new HeapNode(v,0);
  for (int j = 1; j <=n;j++)
   dist[j] = Float.MAX_VALUE;
   dist[v] = 0;
   while(true)
   {
    for(int j = 1; j <= n; j++)
    if(a[enode.i][j] < Float.MAX_VALUE&& enode.length + a[enode.i][j] < dist[j])
    {
     dist[j] = enode.length + a[enode.i][j];
     p[j] = enode.i;
     HeapNode node = new HeapNode(j,dist[j]);
     heap.insert(node);
    }
    if(heap.isEmpty())break;
    else enode = (HeapNode)heap.deleteMin();
   }
    }
public static void main(String[] args)//对给定的有向图，测试最短路径
     {  int [][] a = new int[6][6];
        for(int i = 1;i <6;i++)
          for(int j = 1;j<6;j++)
            a[i][j] = Integer.MAX_VALUE;
      a[1][2] = 10;a[2][3] = 50;a[1][5]=100;a[1][4]=30;
      a[3][5] = 10;a[4][3]=20;a[4][5]=60;
        float [] d = {0,0,0,0,0,0};
      int [] p = {0,0,0,0,0,0};
      shortest(1,d,p,a);
      for(int i = 0;i < d.length;i++)
       System.out.println(d[i]);
       for(int i = 0;i<p.length;i++)
       System.out.println(p[i]);
   }    
}
class UnderflowException extends RuntimeException
{
    /**
     * Construct this exception object.
     * @param message the error message.
     */
    public UnderflowException( String message )
    {
        super( message );
    }
}
interface PriorityQueue//建立优先级队列接口
{
    /**
     * The Position interface represents a type that can
     * be used for the decreaseKey operation.
     */
    public interface Position
    {
        /**
         * Returns the value stored at this position.
         * @return the value stored at this position.
         */
        Comparable getValue( );
    }
    
    /**
     * Insert into the priority queue, maintaining heap order.
     * Duplicates are allowed.
     * @param x the item to insert.
     * @return may return a Position useful for decreaseKey.
     */
    Position insert( Comparable x );    /**
     * Find the smallest item in the priority queue.
     * @return the smallest item.
     * @throws UnderflowException if empty.
     */
    Comparable findMin( );    /**
     * Remove the smallest item from the priority queue.
     * @return the smallest item.
     * @throws UnderflowException if empty.
     */
    Comparable deleteMin( );    /**
     * Test if the priority queue is logically empty.
     * @return true if empty, false otherwise.
     */
    boolean isEmpty( );    /**
     * Make the priority queue logically empty.
     */
    void makeEmpty( );
    
    /**
     * Returns the size.
     * @return current size.
     */
    int size( );
    
    void decreaseKey( Position p, Comparable newVal );
}class BinaryHeap implements PriorityQueue//实现最小堆，实现优先队列接口
{
    /**
     * Construct the binary heap.
     */
    public BinaryHeap( )
    {
        currentSize = 0;
        array = new Comparable[ DEFAULT_CAPACITY + 1 ];
    }
 
    /**
     * Construct the binary heap from an array.
     * @param items the inital items in the binary heap.
     */
    public BinaryHeap( Comparable [ ] items )
    {
        currentSize = items.length;
        array = new Comparable[ items.length + 1 ];
        
        for( int i = 0; i < items.length; i++ )
            array[ i + 1 ] = items[ i ];
        buildHeap( );    
    }
 private void doubleArray()
 {
    Comparable [] tmp;
    tmp= new Comparable[array.length];
    for (int i=0;i<array.length;i++ )
    {
     tmp[i]=array[i];
    }
    array= new Comparable[2*tmp.length];
    for (int i=0;i<tmp.length;i++ )
    {
     array[i]=tmp[i];
    }
  }
    
    /**
     * Insert into the priority queue.
     * Duplicates are allowed.
     * @param x the item to insert.
     * @return null, signifying that decreaseKey cannot be used.
     */
    public PriorityQueue.Position insert( Comparable x )
    {
        if( currentSize + 1 == array.length )
    doubleArray();            // Percolate up
        int hole = ++currentSize;
        array[ 0 ] = x;
        
        for( ; x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 )
            array[ hole ] = array[ hole / 2 ];
        array[ hole ] = x;
        
        return null;
    }    /**
     * @throws UnsupportedOperationException because no Positions are returned
     * by the insert method for BinaryHeap.
     */
    public void decreaseKey( PriorityQueue.Position p, Comparable newVal )
    {
        throw new UnsupportedOperationException( "Cannot use decreaseKey for binary heap" );
    }
        
    /**
     * Find the smallest item in the priority queue.
     * @return the smallest item.
     * @throws UnderflowException if empty.
     */
    public Comparable findMin( )
    {
        if( isEmpty( ) )
            throw new UnderflowException( "Empty binary heap" );
        return array[ 1 ];
    }    /**
     * Remove the smallest item from the priority queue.
     * @return the smallest item.
     * @throws UnderflowException if empty.
     */
    public Comparable deleteMin( )
    {
        Comparable minItem = findMin( );
        array[ 1 ] = array[ currentSize-- ];
        percolateDown( 1 );        return minItem;
    }    /**
     * Establish heap order property from an arbitrary
     * arrangement of items. Runs in linear time.
     */
    private void buildHeap( )
    {
        for( int i = currentSize / 2; i > 0; i-- )
            percolateDown( i );
    }    /**
     * Test if the priority queue is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty( )
    {
        return currentSize == 0;
    }    /**
     * Returns size.
     * @return current size.
     */
    public int size( )
    {
        return currentSize;
    }
    
    /**
     * Make the priority queue logically empty.
     */
    public void makeEmpty( )
    {
        currentSize = 0;
    }    private static final int DEFAULT_CAPACITY = 100;    private int currentSize;      // Number of elements in heap
    private Comparable [ ] array; // The heap array    /**
     * Internal method to percolate down in the heap.
     * @param hole the index at which the percolate begins.
     */
    private void percolateDown( int hole )
    {
        int child;
        Comparable tmp = array[ hole ];        for( ; hole * 2 <= currentSize; hole = child )
        {
            child = hole * 2;
            if( child != currentSize &&
                    array[ child + 1 ].compareTo( array[ child ] ) < 0 )
                child++;
            if( array[ child ].compareTo( tmp ) < 0 )
                array[ hole ] = array[ child ];
            else
                break;
        }
        array[ hole ] = tmp;
    }
}