仅使用邻接矩阵的BFS最短路径？

我正在试图使用邻接矩阵来实现Ford-Fulkerson/Edmonds-Karp。唯一不能编程的是使用BFS计算最短路径的函数。看看最短路径实际存在的功能是好的，但是有可能获得最短路径吗？或者是获得BFS的最短路径使用某种父指针并向后遍历以获取路径的唯一方法？仅使用邻接矩阵的BFS最短路径？

这里是我的代码，看看是否存在路径：

public static boolean existsPathFromSourceToSinkInGf(int Gf[][]) 
{ 
    LinkedList<Integer> queue = new LinkedList<Integer>(); 
    queue.add(0); 

    while (!queue.isEmpty()) 
    { 
     int v = queue.remove(); 
     if (v == sink) return true; 
     for (int i = 0; i < 5; i++) 
     { 

      if (Gf[v][i] != 0) 
      { 
       if (!queue.contains((Integer)i)) 
       { 
        queue.add((Integer)i); 
       } 
      } 
     } 
    } 

    return false; 

    }

来源

2012-11-15 eivindml

是的，你应该使用'parent'并且回溯得到数组。由于你的顶点是整数，所以它可以用一个实际上是'int []'的映射来完成 - 其中'parent [i] =节点i的父节点' – amit

常见的方式做到这一点确实是保持每次解决一个节点，一旦你找到了你的路径倒退时间父指针。

您还可以在队列中明确记录路径。您可以创建自己的类，包含整数和一个类似“node 1-> node 3 - > ...”的字符串，而不是仅为整个链表使用整数。它由于类和路径的开销而不太常用，但它避免了必须自行保留父指针，并且最终必须遍历它们。

在一个侧面说明2名备注您的代码：

为什么它运行对于i = 0..5？
您检查if (!queue.contains((Integer)i))，这样您就不会在已存在的队列上放置顶点。您还应该避免将顶点放在已从列表中移除的顶点上（尝试维护一组访问节点）。

来源

2012-11-16 13:56:52 Origin

仅使用邻接矩阵的BFS最短路径？

回答

相关问题