Estas dos soluciones también funcionan para gráficos dirigidos:
Para cada nodo inicial u, primero puede aplicar un tipo de BFS hasta profundidad k para encontrar un subgrafo que contenga todas las rutas de longitud como máximo k a partir de u:
BFS (vértice u, profundidad k)
si k> 0 yu aún no ha sido visitado
luego
agregue vértice u a nuestro gráfico de solución
para cada vértice v adyacente a u: agregue edge uv a nuestro gráfico de solución; BFS (v, k-1)
de lo contrario no hagas nada
- Cómo tomar una matriz 1d y convertir la matriz en una matriz 2d en una función c ++ para que la matriz ahora sea 2d en main ()
- ¿Cómo se usa la similitud de coseno con el algoritmo K-means?
- ¿Cuáles son algunas formas diferentes de calcular la mediana de una matriz en Java?
- Cómo usar la recursión de la cola de Fibonacci en C ++
- Cómo encontrar proyectos en algoritmo
Luego, al aplicar Dijkstra en este gráfico encontrado, tiene las longitudes que está buscando 🙂
Observe que los vértices no disponibles en este gráfico no se pueden alcanzar con trayectos de longitud como máximo k.
De esta manera, tiene las longitudes mínimas utilizando rutas de longitud como máximo k a partir de u, solo en [math] O (\ text {number_edge} * \ log (\ text {number_edge})). [/ Math]
Aunque este no es el más rápido, una solución simple y hermosa es la siguiente: considere que los vértices de su gráfico están numerados de 1 a n.
Ahora considere la matriz [math] n * n [/ math] M, de modo que [math] M_ {i, j} [/ math] es el peso del borde entre [math] i [/ math] y [math] j [/ math], definido como [math] + \ infty [/ math] si no hay tal borde directo entre [math] i [/ math] y [math] j [/ math], y 0 si [math] i = j [/ matemáticas].
Ahora multiplicaremos las matrices, en lugar de eso, la suma usual se reemplaza por el mínimo, y la multiplicación usual se reemplaza por la suma. Entonces, si [matemática] AB = C [/ matemática], entonces [matemática] C_ {i, j} [/ matemática] es el mínimo de todos [matemática] A_ {i, k} + B_ {k, j} [ / math] para todos los k en {1, …, n}.
Es fácil probar de forma recursiva que, si consideramos [matemáticas] M ^ k [/ matemáticas] (el poder k-ésimo de [matemáticas] M [/ matemáticas]), entonces [matemáticas] M ^ k_ {i, j} [ / math] es la longitud de la ruta más pequeña de vértices como máximo [math] k [/ math] desde [math] i [/ math] a [math] j [/ math], que es exactamente lo que buscas.
Puede calcular fácilmente [matemática] M ^ k [/ matemática] utilizando exponenciación al cuadrado, lo que resulta en un algoritmo [matemático] O \ left (n ^ 3 \ log (n) \ right) [/ math] con una implementación ingenua de multiplicación matricial.
Observe cómo, si desea rutas de longitud exactamente [matemáticas] k [/ matemáticas] , simplemente puede establecer [matemáticas] M_ {i, i} = + \ infty [/ matemáticas]
