2010-06-29 3 views
1

Floyd's algorithm을 사용하여 모든 쌍 최단 경로 행렬을 계산하도록 그래프 구현을 수정합니다. 그래프에는 인접 링크 목록과 매트릭스 구현이 모두 있습니다. 당분간은이 알고리즘에 필요한 인접 행렬을 사용하고 있습니다.Java : 그래프의 가장자리 참조

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;  
} 

제 질문은 어떻게 비교할 수 있도록 weight_matrix 요소를 참조 할 수 있습니까? 내가 ((weight_matrix + weight_matrix[k][j])<weight_matrix[i][j])

당신이 원하는 것을하지 추측

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(); 
} 
} 
+0

정확히 무엇을 비교하려고합니까? – Kiril

+0

if ((weight_matrix + weight_matrix [k] [j]) Nathan

답변

0

: 다음은 개체 매트릭스에있는 에지 클래스입니다. IIRC, 플로이드의는 다음과 같습니다 : 당신의 weight_matrix 무게의 행렬은 마치

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

(자세한 플로이드의 모습 here을). 이 구현에서 크기는 그래프에있는 정점 수입니다. 모든 에지 가중치가 동일한 경우 각 에지는 무게를 가지고 있다면

, 당신은

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

을 할 수있는, 당신은()는 항상 1을 반환하고 짜잔 위해 getValue을 말할 수 있었다.

+0

답변 해 주셔서 감사합니다. 나는 더 나은 구현을 발견했고 그걸로 갈 것입니다. – Nathan