graph-algorithm - 在给定节点网格和一组源节点的情况下查找最大距离

Question

给定一组按 m×n 网格排列的节点（注意：对角节点不连接），以及一组标记为源节点的节点，求节点与源节点之间的最大距离。

例如，对于 4 x 4 网格和 (1, 0) 处的源节点：

0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0

计算从每个节点到其最近源的距离将产生：

1 2 3 4
0 1 2 3
1 2 3 4
2 3 4 5

因此，最大距离为 5。

对于具有 1 个以上源的网格，例如 3 个源节点：

0 0 1 0
1 0 0 0
0 0 0 0
0 0 0 1

计算从每个节点到其最近源的距离将产生：

1 1 0 1
0 1 1 2
1 2 2 1
2 2 1 0

因此，最大距离为 2。

我写了一个算法来解决这个问题，但看起来最坏的情况使它在 O(n^4) 中运行（假设 m == n）：

// MaximumDistances.java

public class MaximumDistances {
    public static void main(String[] args) {
        int[][] sourceNodes = new int[][] {
            {0, 0, 1, 0},
            {1, 0, 0, 0},
            {0, 0, 0, 0},
            {0, 0, 0, 1}
        };

        int maximumDistance = computeMaximumDistance(sourceNodes);
        System.out.println(String.format(
            "The maximum distance in this grid is %d.",
            maximumDistance));
    }

    private static int computeMaximumDistance(int[][] sourceNodes) {
        int m = sourceNodes.length;
        int n = sourceNodes[0].length;

        // Initializes the distance grid. Since none of the sites have been
        // visited yet, the distance to any grid cell with be
        // `Integer.MAX_VALUE`.
        int[][] distanceGrid = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                distanceGrid[i][j] = Integer.MAX_VALUE;
            }
        }

        // If we're at a source site, we mark its distance to each grid cell.
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (sourceNodes[i][j] == 1) {
                    markDistancesFromSourceSite(i, j, distanceGrid);
                }
            }
        }

        // The maximum value in the distance grid will be the maximum distance.
        int maximumDistance = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (distanceGrid[i][j] > maximumDistance) {
                    maximumDistance = distanceGrid[i][j];
                }
            }
        }

        return maximumDistance;
    }

    private static void markDistancesFromSourceSite(int x, int y, int[][] distanceGrid) {
        int m = distanceGrid.length;
        int n = distanceGrid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int distanceToSource = Math.abs(x - i) + Math.abs(y - j);

                if (distanceGrid[i][j] > distanceToSource) {
                    distanceGrid[i][j] = distanceToSource;
                }
            }
        }
    }
}

有没有更快的算法来解决这个问题？

标签： graph-algorithmshortest-path

Answer 1

是的，您可以使用称为多源 BFS 的概念来解决此问题。多源 BFS 的概念与 BFS 类似，但有细微差别。
在普通 BFS 中，我们最初只在队列中推送 1 个节点，而在多源 BFS 中，我们推送所有源节点。
所以推完所有的源节点后，我们就可以做正常的BFS操作来解决问题了。
时间复杂度将为 O(n*m) 。

import java.util.*;
class Pair{

    int x , y , dist;

    Pair(int first , int second){

        this.x = first;
        this.y = second;
        this.dist = 0;
    }

    Pair(int first , int second , int dist){

        this.x = first;
        this.y = second;
        this.dist = dist;
    }
}

public class MultisourceBFS {
    public static void main(String[] args) {
        int[][] sourceNodes = new int[][] {
            {0, 0, 1, 0},
            {1, 0, 0, 0},
            {0, 0, 0, 0},
            {0, 0, 0, 1}
        };

        int maximumDistance = computeMaximumDistance(sourceNodes);
        System.out.println(String.format(
            "The maximum distance in this grid is %d.",
            maximumDistance));
    }

    private static int computeMaximumDistance(int[][] sourceNodes) {
        int m = sourceNodes.length;
        int n = sourceNodes[0].length;

        int maximumDistance = 0;

        int xx[] = {0 , 0 , 1 , -1}; // Normal array to go to up , down , left , right;
        int yy[] = {1 , -1 , 0 , 0}; // Normal array to go to up ,down , left , right

        Queue<Pair> q = new LinkedList<Pair>();
        boolean isVisited[][] = new boolean[m][n]; // An array to check if a cell is visited or not .

        // I am adding all the source nodes to the queue

        for(int i = 0 ; i < m ; ++i)
            for(int j = 0 ; j < n ; ++j)
                if(sourceNodes[i][j]==1){
                    q.add(new Pair(i , j));
                    isVisited[i][j] = true;
                }

        // Now it is going to be normal BFS

        while(!q.isEmpty()){

            Pair node = q.remove();

            for(int k = 0 ; k < 4 ; ++k){

                int new_i = node.x + xx[k];
                int new_j = node.y + yy[k];

                if(new_i >= 0 && new_i < m && new_j >= 0 && new_j < n && isVisited[new_i][new_j]==false){

                    maximumDistance = Math.max(node.dist + 1 , maximumDistance);

                    isVisited[new_i][new_j] = true;

                    q.add(new Pair(new_i , new_j , node.dist + 1));
                }
            }
        }


        return maximumDistance;
    }

}