java - 在未加权图中找到从源到目的地的所有最短路径

Question

我想在未加权的图中找到所有最短路径。在我的第一次尝试中，我设法使用 BFS 只找到一条短路径。我用了一个栈来保存最短路径，一个队列用于BFS。visited vector 用于标记节点是否被访问。这是我在 Java 中所做的:

public ArrayList<Integer> BFS(int source, int dest) {
        ArrayList<Integer> shortestPathList = new ArrayList<Integer>();
        boolean[] visited = new boolean[100];

        Queue<Integer> q = new LinkedList<Integer>();
        Stack<Integer> pathStack = new Stack<Integer>();

        q.add(source);
        pathStack.add(source);
        visited[source] = true;

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : graph.getNeighboursOf(u)) {
                if (!visited[v]) {
                    q.add(v);
                    visited[v] = true;
                    pathStack.add(v);
                    if (u == dest)
                        break;
                }
            }
        }

        // To find the path
        int node, currentSrc = dest;
        shortestPathList.add(dest);
        while (!pathStack.isEmpty()) {
            node = pathStack.pop();
            if (graph.isNeighbor(currentSrc, node)) {
                shortestPathList.add(node);
                currentSrc = node;
                if (node == source)
                    break;
            }
        }

        return shortestPathList;
    }

ArrayList shortestPathList 只包含一条短路径。我是否可以修改此 BFS 以找到所有最短路径，或者我需要制作另一种算法？

Answer 1

在你的代码中，

if (!visited[v]) {...}

确保您将只使用到每个 v 的第一条最短路径。而不是忽略其他路径，您需要考虑所有这些路径(并且只要到达源的路径，您就需要考虑相同的长度是可能的)。

如果您跟踪已访问节点与源的最小距离，那么这将找到到达目的地的所有最短路径:

function shortest_paths_to(dest):

    if dest == source:
        yield path([n])
        return

    for each vertex n in neighbours(dest):

        if distance_from_source(n) < distance_from_source(dest):
           for each path p in shortest_paths_to(n):
               p.append(dest)
               yield p