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

Question

我正在尝试仅使用邻接矩阵来实现 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;

  }

Answer 1

通常的做法确实是在每次设置节点时维护父指针，并在找到路径后返回。

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

旁注 2 对您的代码的评论:

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