Floyd Warshall's Algorithm for Planar Grid Graph
I have a graph like this:
And I applied the graph array like this:
G[i][j][k]
K
has only 4 cells and shows whether a vertex is connected to four neighboring 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
This shows that vertex (1, 1) is connected to two vertices.
I know Floyd Warshall's algorithm for common types of graphs. But how can I implement the Flyod Warshall algorithm for this kind of graphs?
Thank.
source to share
The Floyd-Warshall algorithm would be very inefficient for such a sparse graph. The graph is sparse because each vertex is connected to no more than four other vertices. In a dense graph, a vertex can be connected to N-1 other vertices, where N is the number of vertices in the graph. In this case, the Floyd-Warshall algorithm will be more or less efficient, but still, if you don't need the shortest paths between each pair of vertices or looking for cycles with negative length, consider using a priority queue to find the shortest path between the source and all other vertices: https://en.wikipedia.org/wiki/Dijkstra's_algorithm#Using_a_priority_queue . Or even the width of the first search can be used if the weights of your plot are equal for each edge (unweighted plot).
If you still need the Floyd-Warshall algorithm for your mesh, here it is. Consider a grid N
on M
, indexed by 1, so the maximum record in the grid is G[N][M][...]
. Then the Floyd-Warshall algorithm would be as follows:
// 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;
}
}
}
}
}
}
}
source to share
Your graph view 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 consists of 4 booleans - each indicates whether it is connected (i,j)
to (i-1,j),(i+1,j),(i,j-1),(i,j+1)
, so using the Floyd-Warshall algorithm with this understanding is pretty straight forward when looking at the wikipedia pseudocode :
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 on lines 4-5, where:
for each edge(u,v):
in fact
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 an edge
Also notice that in your graph, the maximum branching ratio (the number of edges connected to a node) is 4. This means the maximum number of edges in the graph |E| <= 4|V|
.
Since your graph is not directional, finding the shortest path for all can be done more efficiently by running BFS from each node, it will take time O(|V|*(|E|+|V|))
, but since |E| <= 4|V|
, this O(|V|^2)
is compared to Floyd-Warshall, which runs in O(|V|^3)
.
source to share