仅使用邻接矩阵的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

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

您还可以显式跟踪队列中的路径。您可以创建自己的类，该类由整数和一个类似“node 1->；node 3->；的字符串组成，而不是仅为linkedlist使用整数。由于类和路径的开销，它不太常用，但它避免了必须单独保留父指针以及最终必须遍历它们

关于代码的旁注2：

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