Java: hace referencia a una ventaja en un gráfico

Question

Estoy modificando una implementación gráfica para calcular la matriz de camino todos los pares más cortos usando algoritmo de Floyd. El gráfico tiene tanto adyacencia lista enlazada y de la matriz implementaciones. Por ahora estoy usando matriz de adyacencia, ya que su necesaria para este algoritmo.

abstract public class GraphMatrix<V,E> extends AbstractStructure<V> implements Graph<V,E>{
/**
 * Number of vertices in graph.
 */
protected int size;          // allocation size for graph
/**
 * The edge data.  Every edge appears on one (directed)
 * or two (undirected) locations within graph.
 */
protected Object data[][];     // matrix - array of arrays
/**
 * Translation between vertex labels and vertex structures.
 */
protected Map<V,GraphMatrixVertex<V>> dict;   // labels -> vertices
/**
 * List of free vertex indices within graph.
 */
protected List<Integer> freeList;    // available indices in matrix
 /**
 * Whether or not graph is directed.
 */
protected boolean directed;  // graph is directed

/**
 * Constructor of directed/undirected GraphMatrix. Protected constructor.
 *
 * @param size Maximum size of graph.
 * @param dir True if graph is to be directed.
 */
protected GraphMatrix(int size, boolean dir)
{
    this.size = size; // set maximum size
    directed = dir;   // fix direction of edges
    // the following constructs a size x size matrix
    data = new Object[size][size];
    // label to index translation table
    dict = new Hashtable<V,GraphMatrixVertex<V>>(size);
    // put all indices in the free list
    freeList = new SinglyLinkedList<Integer>();
    for (int row = size-1; row >= 0; row--)
        freeList.add(new Integer(row));
}

.
.
.

public Object[][] AllPairsShortestPath()
{
    //First, data array needs to be copied to a new array so that it is not corrupted.
    Object[][] weight_matrix = data.clone();
    for(int k = 0; k < size; k++)
    {
        for(int i = 0; i < size; i++)
        {
            for(int j = 0; j < size; j++)
            {
                if((weight_matrix + weight_matrix[k][j])<weight_matrix[i][j])
                {
                  //New shorter path is found   
                }
            }
        }
    }
    return weight_matrix;       
}

Mi pregunta es ¿cómo puedo yo hacer referencia a los elementos weight_matrix de modo que puedan ser comparados? Aquí es la clase de borde que se encuentra en la matriz del objeto:

public class Edge<V,E>
{
/**
 * Two element array of vertex labels.
 * When necessary, first element is source.
 */
protected V here, there;    // labels of adjacent vertices
/**
 * Label associated with edge.  May be null.
 */
protected E 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(V vtx1, V vtx2, E label,
            boolean directed)
{
    here = vtx1;
    there = 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 V here()
{
    return here;
}

/**
 * Returns the second vertex (or source if undirected).
 *
 * @post returns second node in edge
 * 
 * @return A vertex; if directed, the destination.
 */
public V there()
{
    return there;
}

/**
 * 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(E label)
{
    this.label = label;
}

/**
 * Get label associated with edge.
 *
 * @post returns label associated with this edge
 * 
 * @return The label found on the edge.
 */
public E label()
{
    return label;
}

/**
 * Test and set visited flag on vertex.
 *
 * @post visits edge, returns whether previously visited
 * 
 * @return True iff edge was visited previously.
 */
public boolean visit()
{
    boolean was = visited;
    visited = true;
    return was;
}

/**
 * Check to see if edge has been visited.
 *
 * @post returns true iff edge has been visited
 * 
 * @return True iff the edge has been visited.
 */
public boolean isVisited()
{
    return visited;
}

/**
 * Check to see if edge is directed.
 *
 * @post returns true iff edge is directed
 * 
 * @return True iff the edge has been visited.
 */
public boolean isDirected()
{
    return directed;
}

/**
 * Clear the visited flag associated with edge.
 *
 * @post resets edge's visited flag to initial state
 */
public void reset()
{
    visited = false;
}

/**
 * Returns hashcode associated with edge.
 *
 * @post returns suitable hashcode
 * 
 * @return An integer code suitable for hashing.
 */
public int hashCode()
{
    if (directed) return here().hashCode()-there().hashCode();
    else          return here().hashCode()^there().hashCode();
}

/**
 * Test for equality of edges.  Undirected edges are equal if
 * they connect the same vertices.  Directed edges must have same
 * direction.
 *
 * @post returns true iff edges connect same vertices
 * 
 * @param o The other edge.
 * @return True iff this edge is equal to other edge.
 */
public boolean equals(Object o)
{
    Edge<?,?> e = (Edge<?,?>)o;
    return ((here().equals(e.here()) && 
             there().equals(e.there())) ||
            (!directed &&
             (here().equals(e.there()) && 
              there().equals(e.here()))));
}

/**
 * Construct a string representation of edge.
 *
 * @post returns string representation of edge
 * 
 * @return String representing edge.
 */
public String toString()
{
    StringBuffer s = new StringBuffer();
    s.append("<Edge:");
    if (visited) s.append(" visited");
    s.append(" "+here());
    if (directed) s.append(" ->");
    else s.append(" <->");
    s.append(" "+there()+">");
    return s.toString();
}
}

Answer 1

supongo ((weight_matrix + weight_matrix[k][j])<weight_matrix[i][j])

No es lo que quiere. IIRC, de Floyd de la siguiente manera:

((weight_matrix[i][k] + weight_matrix[k][j])<weight_matrix[i][j])

SI SU weight_matrix eran una matriz de pesos (echar un vistazo aquí para obtener más Floyd). Tamaño, en esta aplicación, sería el número de vértices que tienes en el gráfico.

Si cada borde tenía un peso, que podría hacer

(( ((Edge)weight_matrix[i][k]).getValue() + ((Edge)weight_matrix[k][j]).getValue()) < ((Edge)weight_matrix[i][j]).getValue())

Si todos los pesos de las aristas son iguales, se podría decir getValue () para devolver 1 siempre, y listo.