0

我正在尝试仅使用邻接矩阵来实现 Ford-Fulkerson/Edmonds-Karp。我唯一无法编程的是使用 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;

  }
4

1 回答 1

1

做到这一点的常用方法确实是在每次确定节点时维护父指针，并在找到路径后返回。

您还可以明确跟踪队列中的路径。您可以创建自己的类，而不是仅使用整数作为链表，该类由整数和字符串组成，例如“节点 1-> 节点 3->...”。由于类和路径的开销，它不太常用，但它避免了必须自己保留父指针并最终遍历它们。

在旁注 2 对您的代码的评论：

  1. 为什么它运行 i=0..5？
  2. 你检查if (!queue.contains((Integer)i))所以你不要把一个顶点放在你已经在它上面的队列上。您还应该避免将已经从列表中删除的顶点放在上面（尝试维护一组访问节点）。
于 2012-11-16T13:56:52.237 回答