Floyd Warshall算法用于平面网格图(Floyd Warshall Algorithm for a planar grid graph)

Floyd Warshall算法用于平面网格图(Floyd Warshall Algorithm for a planar grid graph)

我有这样的图表：

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

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算法呢？

谢谢。

I have a graph like this:

And I implemented graph array like this:

G[i][j][k]

Khas only 4 cells and it shows whether the vertex is connected to its four neighbor vertices or not. For example for:

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

It shows that the vertex(1, 1) is connected to 2 vertices.

I know the Floyd Warshall algorithm for normal types of graphs. But how can I implement Flyod Warshall Algorithm for this kind of graph?

Thank.

最满意答案

对于这样的稀疏图，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; } } } } } } }

Floyd-Warshall algorithm would be very inefficient for such a sparse graph. The graph is sparse because every vertex connected to no more than 4 other vertices. In a dense graph a vertex can be connected to up to N-1 other vertices, where N is the number of vertices in the graph. That is where Floyd-Warshall algorithm would be more or less efficient, but still, if you don't need shortest paths between each pair of vertices or finding negative-length cycles, consider using priority queue for finding the shortest path between a source and all other vertices: https://en.wikipedia.org/wiki/Dijkstra's_algorithm#Using_a_priority_queue . Or even breadth first search can be used if the weights in your graph are equal for each edge (unweighted graph).

If you still want Floyd-Warshall algorithm for your grid, here it is. Consider the grid is N by M, with 1-based indexing so that the maximal entry in the grid is G[N][M][...]. Then Floyd-Warshall algorithm would be:

// 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; } } } } } } }