我正在尝试仅使用邻接矩阵来实现 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;
}
最佳答案
通常的做法确实是在每次设置节点时维护父指针,并在找到路径后返回。
您还可以在队列中明确跟踪路径。您可以创建自己的类,由整数和字符串组成,例如“节点 1-> 节点 3->...”,而不是只为您的链表使用一个整数。由于类和路径的开销,它不太常用,但它避免了必须保留父指针并最终遍历它们。
旁注 2 对您的代码的评论:
- 为什么它运行 i=0..5?
- 您检查
if (!queue.contains((Integer)i))
这样您就不会在您的队列中放置一个已经存在的顶点。您还应该避免将已从列表中删除的顶点放在上面(尝试维护一组已访问的节点)。
关于java - 仅使用邻接矩阵的 BFS 最短路径?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13405338/