获取从源节点到所有节点的最短距离优化。

Question

我有一个输入为[][]edges的数组。数组的列长度为2。因此，2D数组的每一行都有2个元素。每个元素都是一个顶点。它是双向的，即我们可以说边是双向的。因此，如果我们遍历这个2D数组，我们可以说我们有一个无向图。

我正在尝试找到从一个特定节点到所有节点的最短距离。在这种情况下，从节点0到存在的所有节点。

我有一个可行的代码，但我认为我正在重新计算我想要避免的东西。我一遍又一遍地调用函数computeDistPerNode(m,0,key);，我确信它正在重新计算从0到之前调用中看到的节点的距离。我无法对其进行优化并利用过去的计算。我该怎么做？

以下是未经优化的工作代码

    public Map<Integer, List<Integer>> createUnDirectedGraph(int [][]edges) {
    Map<Integer, List<Integer>> m = new HashMap<>();
    for(var i = 0; i<edges.length; i++) {
        m.put(edges[i][0], new ArrayList<>());
        m.put(edges[i][1], new ArrayList<>());
    }
    for(var edge:edges) {
        var v1 = edge[0];
        var v2 = edge[1];
        m.get(v1).add(v2);
        m.get(v2).add(v1);
    }
    return m;
}

public int[] getShortestDistances(Map<Integer, List<Integer>> m) {
    int distance[] = new int[m.size()];
    for(Integer key:m.keySet()) {
       var d = computeDistPerNode(m,0,key);
       distance[key] = d;
    }
    return distance;
}
public int computeDistPerNode(Map<Integer, List<Integer>> m, int src, int dest) {
    Queue<Integer> q = new LinkedList<>();
    Integer dist[] = new Integer[m.size()];
    Set<Integer> visited = new HashSet<>();
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    q.add(src);
    while(!q.isEmpty()) {
       var currNode = q.poll();
       if(visited.contains(currNode)) continue;
       visited.add(currNode);
       if(currNode == dest) {
           return dist[dest];
       }


       for(var child: m.get(currNode)) {
           if (visited.contains(child)) {
               continue;
           }

           q.offer(child);
           var newDist = 1 + dist[currNode];
           if(newDist<dist[child]) {
               dist[child] = newDist;
           }
       }
    }
    return -1;
}

public int[][] getsample() {
    int [][] edges = {
            {0,1},
            {0,2},
            {1,4},
            {2,3},
            {4,3},
            {0,4},
    };
    return edges;
}

- curiousengineer

Answer 1

您可以一次性计算源节点到所有其他节点的距离。

方法int computeDistPerNode(Map<Integer, List<Integer>> m, int src, int dest)在到达目标节点时立即返回。将其更改为在队列为空时返回dist数组。这是您修改后的方法：

public Integer[] computeDistFromSource(Map<Integer, List<Integer>> m, int src) {
    Set<Integer> visited = new HashSet<>();

    Integer[] dist = new Integer[m.size()];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    Queue<Integer> q = new LinkedList<>();
    q.add(src);

    while(!q.isEmpty()) {
        var currNode = q.poll();
        if(visited.contains(currNode)) continue;
        visited.add(currNode);

        for(var child: m.get(currNode)) {
            if (visited.contains(child)) continue;

            q.offer(child);
            var newDist = 1 + dist[currNode];

            if(newDist < dist[child]) {
                dist[child] = newDist;
            }
        }
    }

    return dist;
}

改进

如果您稍微调整一下代码中的行位置，就可以避免三个if语句的调用。这将导致更干净、更易读的代码。

public Integer[] computeDistFromSource(Map<Integer, List<Integer>> m, int src) {
    Set<Integer> visited = new HashSet<>();

    Integer[] dist = new Integer[m.size()];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    Queue<Integer> q = new LinkedList<>();
    visited.add(src);   // mark source visited here
    q.add(src);

    while(!q.isEmpty()) {
        var currNode = q.poll();

        for(var child: m.get(currNode)) {
            if (!visited.contains(child)) {
                visited.add(child);
                q.offer(child);
                dist[child] = 1 + dist[currNode];
            }
        }
    }

    return dist;
}

分析

使用的算法是广度优先搜索。根据维基百科的说法。

时间复杂度可以表示为O(|V| + |E|)，因为在最坏情况下将探索每个顶点和每条边。 |V|是图中顶点的数量，|E|是图中边的数量。请注意， O（| E |）可能会在O（1）和O（| V | ^ 2）之间变化，具体取决于输入图的稀疏程度。

问题

您能帮我理解为什么新值newDist的较大值可能不会在没有该检查的情况下写入当前的dist [child]吗？ 我认为原因是由于BFS /使用队列的性质，当未访问的节点被拉出时，子级将首先被访问，因此不需要进行检查？

if(newDist < dist[child]) 条件在您的代码中是必要的，以确保正确运行。在优化后的代码中不需要此条件。原因是 visited.add(child) 的位置不同。在您的代码中，该检查发生在从队列中轮询节点之后。在优化后的代码中，这会在发现节点后立即发生。这会产生很大的差异。

考虑您的输入图

0 ------- 1
|\        |
|  \      |
|    \    | 
|      \  |
|        \|
|         4
|         |
|         |
|         |
2 ------- 3

代码的工作原理

源顶点为0。在循环while (!q.isEmpty()开始之前，我们将其添加到队列中。

在while循环中，我们删除0并将其标记为已访问。我们按顺序探索其邻居1、2和4。我们将它们的距离更新为1，并将它们全部添加到队列中。然而，它们中没有一个被标记为已访问。

现在我们回到while循环的开头，轮询1，将其标记为已访问，并再次探索其邻居0和4。我们不更新0的距离，因为它已经被访问过了。即使4已经是队列的一部分，我们仍将其再次添加到队列中。我们已经在队列中添加了相同的节点，这本身就不是好事。请注意，如果没有if(newDist < dist[child])条件，它的距离将被更新为错误的2。

优化后代码的工作原理

源顶点为0。在循环while (!q.isEmpty()开始之前，我们将其添加到队列中并在此处标记为已访问。

在 while 循环中，我们删除 0。按照顺序探索其邻居 1、2 和 4。我们将它们的距离更新为 1，并将它们全部添加到队列中，并标记它们为已访问。因此，它们的距离永远不会再次更新。

现在我们回到 while 循环的开始，poll 1 并再次探索其邻居 0 和 4。我们不更新 0 和 1 的距离，因为它们都已被访问过。节点 4 也不会被重复添加到队列中。

- AKSingh

---

谢谢。我有一个问题。我认为即使在您优化的代码和我的代码中，不需要if(newDist < dist[child]) {的原因是因为visited会自然地处理它，如果没有访问过，则newDist始终较小？您能帮我理解一下吗？如何在没有该检查的情况下，可能不会将较大的newDist值写入当前的dist[child]中？我认为原因是由于BFS /使用队列的性质，当未访问的节点被拉出时，子节点将首先被访问，因此不需要进行检查？ - curiousengineer

它还没有被访问，新的距离（newDist）将始终较小。是的，BFS遍历的性质确保我们第一次访问任何节点时，到达该节点的距离将是最短的。有很多相关资源可供参考。你应该阅读它们，它们非常精彩。 - AKSingh

你能帮我理解如果没有这个检查，一个更大的newDist值可能不会被写入当前的dist[child]吗？- 我已经在更新后的答案中回答了这个问题，因为它有点长。我通过一个示例图和代码的简短运行来解释了它。你的直觉并不完全正确 - 我认为原因是由于BFS/使用队列的性质，当一个未访问的节点被拉出时，一个子节点将首先被访问，因此不需要进行检查。 - AKSingh

Answer 2

如果您使用min-priority-queue或min-heap，则可以将算法复杂度降至O（|V| * |E|），即顶点数和边数的乘积。即使从@AKSingh的answer中改进了算法，我认为它仍然是O（|V|^2）。

维基百科有一个很好的Dijkstra算法描述，这是解决使用min-priority-queue的最小路径问题的标准技术。这里是一个更加教程式的描述，其中包含许多图形来可视化算法。

以下是实现该算法的一些示例代码。很抱歉它不是用Java编写的，但翻译应该很简单。

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using NodePair = std::pair<int,int>;
using NodePairs = std::vector<NodePair>;

using DistanceVertex = std::pair<int, int>;
using MinQueue = std::priority_queue<DistanceVertex,
                                  std::vector<DistanceVertex>,
                                  std::greater<DistanceVertex>>;

int main(int argc, const char *argv[]) {
    // The sample problem. We store the graph as a adjacency list
    // using a multimap.
    std::multimap<int, int> edges {
        { 0, 1 },
        { 0, 2 },
        { 1, 4 },
        { 2, 3 },
        { 4, 3 },
        { 0, 4 }
    };

    // How many vertices?
    int max_vertex{};
    for (auto [a, b] : edges) {
        max_vertex = std::max(max_vertex, a);
        max_vertex = std::max(max_vertex, b);
    }
    int number_vertices = max_vertex + 1;

    // Initialize the distance from source to each vertex as MAX_INT.
    int source{};
    std::vector<int> distance(number_vertices, std::numeric_limits<int>::max());

    // Initialize distance to source and priority queue
    MinQueue pq;
    distance[source] = 0;
    pq.emplace(0, source);

    while (!pq.empty()) {
        auto [udist, udx] = pq.top();
        pq.pop();

        // Iterate over all neighbors of vdx
        auto [begin, end] = edges.equal_range(udx);
        for (auto iter = begin; iter != end; ++iter) {
            auto vdx = iter->second, vdist = iter->first;

            // If there is a shorter path, record it
            if (udist + vdist < distance[vdx]) {
                distance[vdx] = udist + vdist;
                pq.push({udist, vdx});
            }
        }
    }

    // distance now contains the shortest distance between source and each node
    for (auto i = 0; i < number_vertices; ++i)
        std::cout << distance[i] << std::endl;

    return 0;
}

- RandomBits

---

我提到的代码是一个简单的“BFS”遍历。 BFS的时间复杂度为“O(|V| + |E|)”。Dijkstra算法的复杂度为“Θ（|E| + |V|log⁡|V|）”。需要注意的是，在最坏的情况下，“|E| = O(|V^2|)” ，这将把BFS和Dijkstra的复杂度都转化为“O(|V|^2)”。 - AKSingh