平面网格图的Floyd 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:

Khas只有4个单元格，它显示了顶点是否连接到它的四个相邻顶点。例如:

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.

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

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

我知道Floyd Warshall算法的正常类型的图形。但是如何实现这种图的Flyod Warshall算法呢?

Thank.

谢谢。

2 个解决方案

#1

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).

Floyd-Warshall算法对于这样的稀疏图是非常低效的。图形是稀疏的，因为每个顶点连接到不超过4个其他顶点。在稠密图中，顶点可以连接到N-1其他顶点，其中N是图中顶点的数目。这就是Floyd-Warshall算法效率更高或更低的地方，但是，如果你不需要每对顶点之间的最短路径，或者找到负长度的周期，考虑使用优先队列寻找源和所有其他顶点之间的最短路径:https://en.wikipedia.org/wiki/Dijkstra的_algorithm#Using_a_priority_queue。如果你的图中的权值与每条边相等(未加权图)，甚至可以使用广度优先搜索。

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:

如果你仍然想要Floyd-Warshall算法的网格，在这里。考虑网格为N×M，以1为基础的索引，使网格中最大的项为G[N][…]。然后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;
                        }
                    }
                }
            }
        }
    }
}

#2

Your graph representation is basically an adjacency list, for each vertex v= G[i][j], you have a list containing the edges the graph is connected to. In your case, the list is made by 4 boolean values - each is indicating if the (i,j) is connected to (i-1,j),(i+1,j),(i,j-1),(i,j+1), so using Floyd-Warshall algorithm with that understanding is pretty straight forward, if looking on the wikipedia pseudo code:

您的图形表示基本上是一个邻接表，对于每个顶点v= G[i][j]，您有一个包含图所连接到的边的列表。在你的例子中，列表是由4个布尔值构成的——每个值都表示如果(i,j)连接到(i-1,j)，(i+1,j)，(i,j-1)，(i,j+1)，那么使用Floyd-Warshall算法的理解是非常直接的，如果查看wikipedia伪代码:

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    dist[v][v] ← 0
4 for each edge (u,v)
5    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

The main difference is in lines 4-5, where:

主要区别在第4-5行，其中:

for each edge(u,v):

is actually

实际上是

for each x=0,1,...,n-1
   for each y=0,1,...,m-1
       for each i=0,1,2,3:
             //if G[x][y][y] == 1 : it's an edge

---

Also note, in your graph, the maximum branch factor (number of edges connected to a node) is 4. This means, maximum number of edges in the graph is |E| <= 4|V|.
Since your graph is not directed, finding all-to-all shortest path can be done more efficiently by doing a BFS from each node, it will take O(|V|*(|E|+|V|)) time, but since |E| <= 4|V|, this is O(|V|^2) - compared to Floyd-Warshall which runs in O(|V|^3).

还要注意，在您的图中，最大分支因子(连接到节点的边数)为4。这意味着，图中最大的边数是|E| <= 4|V|。自你的图不是导演,找到所有最短路径可以更有效地完成从每个节点,通过BFS还需要O(V | | *(V E | | + | |)),但由于| E | < = 4 V | |这是O(V | | ^ 2)——Floyd-Warshall相比在O(V | | ^ 3)。