title: Java: Using adjacency list to compute all pairs shortest path?
body: <p>I am writing a Graph library that has both adjacency list and matrix implementations. Here is some code I came across in a Java data structures textbook:</p>
  
  <pre><code>static void floyd(Graph&lt;V,E&gt; g) 
  // post: g contains edge (a,b) if there is a path from a to b 
  {
       Iterator&lt;V&gt; witer = g.iterator();   //vertex iterator
       while (witer.hasNext())
       {
          Iterator&lt;V&gt; uiter = g.iterator(); 
          V w = witer.next(); 
          while (uiter.hasNext())
          {
              Iterator&lt;V&gt; viter = g.iterator();
              V u = uiter.next(); 
              while (viter.hasNext())
              {
                  V v = viter.next(); 
                  if (g.containsEdge(u,w) &amp;&amp; g.containsEdge(w,v)) 
                  {
                       Edge&lt;V,E&gt; leg1 = g.getEdge(u,w);
                       Edge&lt;V,E&gt; leg2 = g.getEdge(w,v); 
                       int leg1Dist = leg1.label(); 
                       int leg2Dist = leg2.label(); 
                       int newDist = leg1Dist+leg2Dist;
  
                       if (g.containsEdge(u,v)) 
                       {
                           Edge&lt;V,E&gt; across = g.getEdge(u,v); 
                           int acrossDist = across.label(); 
                           if (newDist &lt; acrossDist)
                             across.setLabel(newDist); 
                        } 
                        else 
                        {
                             g.addEdge(u,v,newDist);
                         }
                    }
               }
           }
       }
  </code></pre>
  
  <p>But it seems like it is just overwriting the current edge with with the "shortest". Is this interpretation correct? I could use some clarification here.</p>
  
  <p>Note: Here is some of the Edge class:</p>
  
  <pre><code>public class Edge
  {
  /**
   * Two element array of vertex labels.
   * When necessary, first element is source.
   */
  protected Object[] vLabel;  // labels of adjacent vertices
  /**
   * Label associated with edge.  May be null.
   */
  protected Object label;     // edge label
  /**
   * Whether or not this edge has been visited.
   */
  protected boolean visited;  // this edge visited
  /**
   * Whether or not this edge is directed.
   */
  protected boolean directed; // this edge directed
  
  /**
   * Construct a (possibly directed) edge between two labeled
   * vertices.  When edge is directed, vtx1 specifies source.
   * When undirected, order of vertices is unimportant.  Label
   * on edge is any type, and may be null.
   * Edge is initially unvisited.
   *
   * @post edge associates vtx1 and vtx2; labeled with label
   *       directed if "directed" set true
   *
   * @param vtx1 The label of a vertex (source if directed).
   * @param vtx2 The label of another vertex (destination if directed).
   * @param label The label associated with the edge.
   * @param directed True iff this edge is directed.
   */
  public Edge(Object vtx1, Object vtx2, Object label,
              boolean directed)
  {
      vLabel = new Object[2];
      vLabel[0] = vtx1;
      vLabel[1] = vtx2;
      this.label = label;
      visited = false;
      this.directed = directed;
  }
  
  /**
   * Returns the first vertex (or source if directed).
   *
   * @post returns first node in edge
   * 
   * @return A vertex; if directed, the source.
   */
  public Object here()
  {
      return vLabel[0];
  }
  
  /**
   * Returns the second vertex (or source if undirected).
   *
   * @post returns second node in edge
   * 
   * @return A vertex; if directed, the destination.
   */
  public Object there()
  {
      return vLabel[1];
  }
  
  /**
   * Sets the label associated with the edge.  May be null.
   *
   * @post sets label of this edge to label 
   * 
   * @param label Any object to label edge, or null.
   */
  public void setLabel(Object label)
  {
      this.label = label;
  }
  
  /**
   * Get label associated with edge.
   *
   * @post returns label associated with this edge
   * 
   * @return The label found on the edge.
   */
  public Object label()
  {
      return label;
  }
  </code></pre>