时间戳

首页 > 解决方案 > 如何在线性时间内找到无向图中不同最短路径的数量？

algorithm - 如何在线性时间内找到无向图中不同最短路径的数量？

问题描述

给定一条无向路径，在输入起始节点 u 和结束节点 v 后，不同最短路径数的算法是什么？该算法可以依赖于 |V| 和|E|，但就每一个而言必须是线性的。

证明它实际上返回任何 u 和 v 的不同最短路径的数量也会有所帮助。

标签： algorithmgraph-theory

解决方案

我认为你正在寻找这样的东西：

注意：图存储为邻接表

public int shortestPath(int u, int v, ArrayList<Integer>[] adj) {
    Queue<Integer> bfs = new ArrayDeque();
    bfs.add(u);

    int ret = 0;

    boolean[] visited = new boolean[adj.length];

    while (!bfs.isEmpty() && (ret == 0 || bfs.peek() == v)) {
        int node = bfs.poll();
        visited[node] = true;

        if (node == v) {
            ret++;
        }

        for (int next : adj[node]) {
            if (!visited[next]) {
                bfs.add(next);
            }
        }
    }
    return ret;
}

想法在评论中，但本质上你正在运行一个 bfs，并跟踪有多少路径访问 v 当第一条路径访问 v。注意我是如何将节点设置为已访问的，只有在我从队列中轮询它之后，这是需要的计算路径的数量。

如果您仍然感到困惑，请告诉我

推荐阅读