У меня есть такой график:
И я реализовал массив графов следующим образом:
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 вершинами.
Я знаю алгоритм Флойда Уоршалла для нормальных типов графиков. Но как я могу реализовать алгоритм Флайода Варшалла для такого типа графа?
Благодарить.
Алгоритм Флойда-Уоршалла был бы очень неэффективен для такого разреженного графа. Граф является разреженным, потому что каждая вершина связана не более чем с 4 другими вершинами. В плотном графе вершина может быть соединена с N-1 другими вершинами, где N - количество вершин в графе. Вот где алгоритм Флойда-Уоршалла был бы более или менее эффективным, но все же, если вам не нужны кратчайшие пути между каждой парой вершин или поиск циклов отрицательной длины, подумайте об использовании очереди с приоритетами для поиска кратчайшего пути между источником и все остальные вершины: https://en.wikipedia.org/wiki/Dijkstra. Или даже поиск в ширину может использоваться, если веса в вашем графике равны для каждого ребра (невзвешенный граф).
Если вам все еще нужен алгоритм Флойда-Уоршалла для вашей сетки, вот он. Предположим, что сетка имеет размер N на M, с индексированием на основе 1, так что максимальная запись в сетке равна G[N][M][...]. Тогда алгоритм Флойда-Уоршалла будет:
// 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;
}
}
}
}
}
}
}
Представление вашего графа в основном представляет собой список смежности, для каждой вершины v= G[i][j] у вас есть список, содержащий ребра граф связан с. В вашем случае список состоит из 4 логических значений - каждое указывает, подключен ли (i,j) к (i-1,j),(i+1,j),(i,j-1),(i,j+1), поэтому использование алгоритма Флойда-Уоршалла с таким пониманием довольно просто, если смотреть на псевдокод википедии:
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
Основное различие в строках 4-5, где:
for each edge(u,v):
на самом деле
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
Также обратите внимание, что в вашем графике максимальный фактор ветвления (количество ребер, соединенных с узлом) равен 4. Это означает, что максимальное количество ребер в графе равно |E| <= 4|V|.
Поскольку ваш график не является направленным, поиск кратчайшего пути от всех ко всем можно сделать более эффективно, выполнив BFS от каждого узла, это займет O(|V|*(|E|+|V|)) времени, но с |E| <= 4|V| это O(|V|^2) - по сравнению с Floyd-Warshall, который работает в O(|V|^3).
