平面网格图的 Floyd Warshall 算法

Question

我有一个这样的图表：

我实现了这样的图形数组：

G[i][j][k]

K只有 4 个单元格，它显示该顶点是否与其四个相邻顶点相连。例如对于：

G[1][1][0] = 0 
G[1][1][1] = 1 
G[1][1][2] = 1 
G[1][1][3] = 0

它表明顶点(1, 1) 连接到2 个顶点。

我知道用于普通类型图的 Floyd Warshall 算法。但是我如何为这种图实现 Flyod Warshall 算法呢？

感谢。

Answer 1

对于这样的稀疏图，Floyd-Warshall 算法的效率非常低。该图是稀疏的，因为每个顶点连接到的其他顶点不超过 4 个。在稠密图中，一个顶点最多可以连接到 N-1 个其他顶点，其中 N 是图中顶点的数量。这就是 Floyd-Warshall 算法效率或多或少的地方，但是，如果您不需要每对顶点之间的最短路径或查找负长度循环，请考虑使用优先级队列来查找源和点之间的最短路径所有其他顶点：https://en.wikipedia.org/wiki/Dijkstra's_algorithm#Using_a_priority_queue。如果图中每条边的权重相等（未加权图），甚至可以使用广度优先搜索。

如果您仍然需要 Floyd-Warshall 算法用于您的网格，这里就是。考虑网格N为M，索引从 1 开始，因此网格中的最大条目为G[N][M][...]。那么 Floyd-Warshall 算法将是：

// edge offsets
const int offs[4][2] = {
    {-1, 0}, {0, 1}, {1, 0}, {0, -1}
};
const int INF_DIST = 1e9;
int D[N+1][M+1][N+1][M+1];
//// Initialize weights to infinity
// For each source row and column (i,j)
for(int i=1; i<=N; i++) {
    for(int j=1; j<=M; j++) {
        // For each destination row and column (k,l)
        for(int k=1; k<=N; k++) {
            for(int l=1; l<=M; l++) {
                D[i][j][k][l] = INF_DIST;
            }
        }
    }
}
//// Mark edges of the graph
// For each row
for(int i=1; i<=N; i++) {
    // For each column
    for(int j=1; j<=M; j++) {
        // For each of the directions: up(k=0), right(k=1), down(k=2) and left(k=3)
        for(int k=0; k<=3; k++) {
            if(G[i][j][k] == 0) {
                // Don't add this edge to the distance matrix
                //   if the edge is not in the grid graph
                continue;
            }
            // Calculate (r, c) as the coordinates of the vertex one step 
            //   in the direction k
            int r = i + offs[k][0];
            int c = j + offs[k][1];
            if(1<=r && r <= N && 1<=c && c<=M) {
                // Only add the edge (if exists) in case (r, c) is within the grid
                D[i][j][r][c] = G[i][j][k];
            }
        }
    }
}
//// Find shortest paths between each pair of vertices
// For each intermediate vertex (k,l)
for(k=1; k<=N; k++) {
    for(l=1; l<=M; l++) {
        // For each source vertex (i,j)
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {
                // For each destination vertex (r,c)
                for(int r=1; r<=N; r++) {
                    for(int c=1; c<=M; c++) {
                        // Apply the triangle rule
                        int alternative = D[i][j][k][l] + D[k][l][r][c];
                        if(alternative < D[i][j][r][c]) {
                            D[i][j][r][c] = alternative;
                        }
                    }
                }
            }
        }
    }
}