0

我正在编写一个同时具有邻接列表和矩阵实现的图形库。这是我在 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;
}
4

1 回答 1

4

如果您使用矩阵将结果存储在矩阵中，则更容易理解您在做什么。考虑以下简单的加权图：

       2
1 +---------+ 2
  |\        |
  | -\      |
3 |   -\5   | 2
  |     -\  |
  |       -\|
3 +---------+ 4
        4

现在考虑Floyd-Warshall 算法的这种实现：

public Matrix floyd() {
  Matrix m = new Matrix(numVertices, numVertices, Integer.MAX_VALUE);
  for (int i = 1; i<=numVertices; i++) {
    EdgeNode edge = edges[i];
    while (edge != null) {
      m.setData(i, edge.getY(), edge.getWeight());
      edge = edge.getNext();
    }
    m.setData(i, i, 0);
  }
  for (int i = 1; i <= numVertices; i++) {
    for (int j = 1; j <= numVertices; j++) {
      for (int k = 1; k <= numVertices; k++) {
        if (m.getData(i, j) < Integer.MAX_VALUE && m.getData(i, k) < Integer.MAX_VALUE) {
          int through = m.getData(i, j) + m.getData(i, k);
          if (through < m.getData(j, k)) {
            m.setData(j, k, through);
          }
        }
      }
    }
  }
  return m;
}

这部分的第一部分为矩阵结果提供种子Integer.MAX_VALUE。将 0 放在这里会产生不正确的结果，但使用 1 和 0 的值（分别）对于未加权的图来说效果很好。Integer.MAX_VALUE是否只是为了正确的最小值检查。

第二部分是算法的关键部分。它查看两点 (i,k) 之间的距离，将其与所有顶点 j 的 (i,j) + (j,K) 的距离进行比较。如果间接路径较少，则将其作为最短路径代入矩阵，依此类推。

该算法在上述（非常简单）图上的结果是：

[ 0 2 3 5 ]
[ 2 0 5 3 ]
[ 3 5 0 4 ]
[ 5 3 4 0 ]

这告诉你的是任何一对顶点之间的最短距离。注意：我已经将 (i,i) 的结果设置为 0，因为您可以说任何节点到自身的距离都是 0。您可以很容易地取出该假设，得到以下结果：

[ 4 2 3 5 ]
[ 2 4 5 3 ]
[ 3 5 6 4 ]
[ 5 3 4 6 ]

因此，节点 3 到自身的距离为 6，因为它以 3->1->3 作为最短路径遍历。这在 Floyd 可以处理的有向图中会变得更加有趣。

Floyd 是一种 O(n 3 ) 算法。它不会重建每对点之间的实际路径，只会重建总距离（权重）。您可以在每个顶点对之间使用Dijkstra 算法来构造实际路径，有趣的是，这也是 O(n 3 )，但在实际使用中往往较慢，因为 Floyd 的计算非常简单。

您的算法使用邻接列表而不是矩阵来实现此算法，这使问题略有混淆。我的版本Integer.MAX_VALUE用作标记值以指示没有路径（尚未计算），而您的版本使用没有边缘来表示同一件事。除此之外，它完全一样。

于 2010-07-15T04:11:08.123 回答