隣接リストと行列の両方の実装を持つグラフ ライブラリを作成しています。Javaデータ構造の教科書で見つけたコードを次に示します。
static void floyd(Graph<V,E> g)
// post: g contains edge (a,b) if there is a path from a to b
{
Iterator<V> witer = g.iterator(); //vertex iterator
while (witer.hasNext())
{
Iterator<V> uiter = g.iterator();
V w = witer.next();
while (uiter.hasNext())
{
Iterator<V> viter = g.iterator();
V u = uiter.next();
while (viter.hasNext())
{
V v = viter.next();
if (g.containsEdge(u,w) && g.containsEdge(w,v))
{
Edge<V,E> leg1 = g.getEdge(u,w);
Edge<V,E> leg2 = g.getEdge(w,v);
int leg1Dist = leg1.label();
int leg2Dist = leg2.label();
int newDist = leg1Dist+leg2Dist;
if (g.containsEdge(u,v))
{
Edge<V,E> across = g.getEdge(u,v);
int acrossDist = across.label();
if (newDist < acrossDist)
across.setLabel(newDist);
}
else
{
g.addEdge(u,v,newDist);
}
}
}
}
}
しかし、現在のエッジを「最短」で上書きしているようです。この解釈は正しいでしょうか？ここでいくつかの説明を使用できます。
注: Edge クラスの一部を次に示します。
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;
}