java - 对顶点列表实现 Floyd-Warshall 算法

Question

我试图从顶点列表返回传递闭包，但我如何使用弗洛伊德·沃歇尔算法来做到这一点？互联网上的所有示例都是以二维数组给出的，但它也可以用于列表吗？示例 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)+" ");
   }
}