c++ - Floyd Warshall Algorithm for a planar grid graph -

i have graph this:

and implemented graph array this:

g[i][j][k] 

khas 4 cells , shows whether vertex connected 4 neighbor vertices or not. example for:

g[1][1][0] = 0  g[1][1][1] = 1  g[1][1][2] = 1  g[1][1][3] = 0 

it shows vertex(1, 1) connected 2 vertices.

i know floyd warshall algorithm normal types of graphs. but how can implement flyod warshall algorithm kind of graph?

thank.

floyd-warshall algorithm inefficient such sparse graph. graph sparse because every vertex connected no more 4 other vertices. in dense graph vertex can connected n-1 other vertices, n number of vertices in graph. floyd-warshall algorithm more or less efficient, still, if don't need shortest paths between each pair of vertices or finding negative-length cycles, consider using priority queue finding shortest path between source , other vertices: https://en.wikipedia.org/wiki/dijkstra's_algorithm#using_a_priority_queue . or breadth first search can used if weights in graph equal each edge (unweighted graph).

if still want floyd-warshall algorithm grid, here is. consider grid n m, 1-based indexing maximal entry in grid g[n][m][...]. floyd-warshall algorithm 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 infinity // each source row , column (i,j) for(int i=1; i<=n; i++) {     for(int j=1; j<=m; j++) {         // each destination row , 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 graph // each row for(int i=1; i<=n; i++) {     // each column     for(int j=1; j<=m; j++) {         // each of directions: up(k=0), right(k=1), down(k=2) , left(k=3)         for(int k=0; k<=3; k++) {             if(g[i][j][k] == 0) {                 // don't add edge distance matrix                 //   if edge not in grid graph                 continue;             }             // calculate (r, c) coordinates of vertex 1 step              //   in direction k             int r = + offs[k][0];             int c = j + offs[k][1];             if(1<=r && r <= n && 1<=c && c<=m) {                 // add edge (if exists) in case (r, c) within grid                 d[i][j][r][c] = g[i][j][k];             }         }     } } //// find shortest paths between each pair of vertices // each intermediate vertex (k,l) for(k=1; k<=n; k++) {     for(l=1; l<=m; l++) {         // each source vertex (i,j)         for(int i=1; i<=n; i++) {             for(int j=1; j<=m; j++) {                 // each destination vertex (r,c)                 for(int r=1; r<=n; r++) {                     for(int c=1; c<=m; c++) {                         // apply 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;                         }                     }                 }             }         }     } }