我有这样的图表:
我实现了这样的图形数组:
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] = 0It 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; } } } } } } }更多推荐
发布评论