Java: Использование списка смежности для вычисления всех пар кратчайшего пути?

Question

Я пишу библиотеку Graph, которая имеет как список смежности, так и матричные реализации.Вот некоторый код, с которым я столкнулся в учебнике по структурам данных 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;
}

Answer 1

Было бы легче понять, что вы делаете, если вы используете матрицу для сохранения результата в матрице.Рассмотрим следующий простой взвешенный граф:

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

Теперь рассмотрим эту реализацию алгоритма Флойд-Варшалла :

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), сравнивая его с расстоянием (i, j) + (j, K) для всех вершин j.Если косвенный путь меньше, он подставляется в матрицу как кратчайший путь и т. Д.

Результат этого алгоритма на приведенном выше (очень простом) графике:

[ 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 как кратчайший путь.Это было бы намного интереснее в ориентированном графе, который может обрабатывать Флойд.

Флойд - алгоритм O (n ³ ).Он не будет реконструировать фактический путь между каждой парой точек, только общее расстояние (вес).Вы можете использовать алгоритм Дейкстры между каждой парой вершин, чтобы построить фактические пути, что довольно интересно, также O (n ³ ), но имеет тенденцию быть медленнее в реальном мире, как вычисленияФлойд довольно прост.

Ваш алгоритм использует список смежности вместо матрицы для реализации этого алгоритма, что немного запутывает проблему.Моя версия использует Integer.MAX_VALUE в качестве часового значения, чтобы указать отсутствие пути (пока не рассчитано), тогда как ваша использует отсутствие ребра для той же вещи.Кроме того, это точно так же.