顶点列表的Floyd-Warshall算法的实现

Question

我正在尝试从顶点列表中返回传递闭包，但我如何使用floyd warshall算法来做到这一点？互联网上的所有示例都是以2D数组的形式给出的，但是它也可以用于列表吗？示例G= ABCD --> G+ = AB AC AD BC BD CD，其中G是顶点列表，G+是传递闭包。

我的实现(错误的方式)：

 public Graph transitiveClosure(LinkedList<Vertex> v)
  {

      String graaf = "";      
      Edge e;
      StringBuffer sb = new StringBuffer(graaf);

      Iterator<Vertex> i = v.iterator();
      Vertex tmp;
      for(Vertex vertex : v)
      {
         System.out.print(vertex);
      }

         while(i.hasNext()) {         
        int next = (v.size() + 1) - v.size();                                        
         tmp =(Vertex) i.next();

         if(tmp == v.getFirst()) 
        tmp = (Vertex)i.next();
        e = new Edge(v.getFirst().toString() + tmp);                        
        sb.append(e); 

         if(tmp == v.get(next)) 
         next++;
         e = new Edge(v.get(next).toString() + tmp);
         sb.append(e);


    }

      System.out.println();

      return new Graph(sb.toString());
      }              
} 

Answer 1

既然你想要所有的(i，j)对，其中i和j是i小于j的索引，我不太明白为什么你想要Floyd-Warshall在这里。

int size = v.size();
StringBuffer sb = new StringBuffer(graaf);
for (int i=0;i<size;i++) {
   for (int j=i+1;j<size;j++) {
      sp.append(v.get(i)+v.get(j)+" ");
   }
}