Compartir tecnología

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Tabla de contenido

algoritmo de floyd

definición

Uso

Precauciones

Ideas para resolver problemas

Los pasos básicos

AcWing 343. Clasificación

Descripción de la pregunta

Ejecutar código

Ideas de código

Mejorar ideas

algoritmo de floyd

definición

El algoritmo de Floyd, el nombre completo del algoritmo Floyd-Warshall, es un algoritmo de programación dinámica que se utiliza para resolver el problema del camino más corto entre todos los pares de vértices del gráfico. Es adecuado para gráficos dirigidos ponderados y puede manejar bordes de peso negativos (pero no gráficos que contengan ciclos de peso negativos) y puede detectar si hay ciclos de peso negativos en el gráfico.

Uso

1. Calcular el camino más corto entre todos los pares de vértices.: En campos como el análisis de redes sociales, la planificación de redes de transporte, el diseño de redes de comunicaciones, etc., el algoritmo Floyd es una buena opción cuando es necesario calcular la distancia más corta entre dos puntos cualesquiera.
2. Detectar ciclos de peso negativos: En algunos escenarios de aplicación, es necesario asegurarse de que no haya ciclos de peso negativos en el gráfico, ya que esto puede indicar alguna anomalía o estado de error en el sistema.

Precauciones

• consumo de memoria : La complejidad espacial del algoritmo de Floyd es O (n^2), donde n es el número de vértices del gráfico. Para gráficos a gran escala, esto puede convertirse en un problema.
• complejidad del tiempo: La complejidad temporal del algoritmo de Floyd es O (n ^ 3). Cuando el número de vértices es grande, el algoritmo puede volverse muy lento.
• bucle de peso negativo : Si hay un ciclo de peso negativo en el gráfico, el algoritmo de Floyd caerá en un bucle infinito, porque a partir de un nodo, la longitud de la ruta se puede reducir infinitamente a través de este ciclo. En aplicaciones prácticas, estas situaciones deben detectarse y manejarse primero.
• Los algoritmos pueden detectar ciclos de peso negativos:Si durante la ejecución del algoritmo se encuentra que el camino más corto desde un vértice hacia sí mismo es menor que 0, es decir, D[i][i] < 0, entonces hay al menos un ciclo de peso negativo en el gráfico, y el algoritmo no puede dar el resultado correcto de la ruta más corta en este momento.
• Para gráficos muy grandes, la alta complejidad temporal y espacial del algoritmo puede convertirse en un cuello de botella. En este momento, es posible que deba considerar algoritmos más eficientes o utilizar estructuras de datos y técnicas de optimización más profesionales.

Ideas para resolver problemas

La idea central del algoritmo de Floyd es la programación dinámica y sus pasos básicos son los siguientes:

1. Inicialización: establezca la matriz de distancia D en la matriz de adyacencia del gráfico, es decir, D [i] [j] = peso (i, j para i! = j, si (i, j) no está conectado, entonces); D[i][j] = ∞; D[i][i] = 0.
2. Programación dinámica: Para k = 1 an, actualice D de manera que D[i][j] = min(D[i][j], D[i][k] + D[k][j]), que es Compruebe si la distancia de i a j se puede acortar a través del nodo intermedio k.
3. Resultado: la matriz D final contiene las longitudes de camino más cortas entre todos los pares de vértices. Si hay un cierto D [i] [j] <0 e i! = j, y D [i] [i] <0 ocurre durante el proceso de actualización, significa que hay un ciclo de peso negativo en el gráfico.

La implementación del algoritmo de Floyd generalmente utiliza un bucle triple. El bucle externo atraviesa todos los vértices intermedios k y los dos bucles internos atraviesan todos los pares de vértices (i, j) para verificar si hay un camino más corto.

Los pasos básicos

Supongamos que tenemos un gráfico ponderado G que contiene n vértices, podemos usar una matriz bidimensionaldist[][] para almacenar la longitud de ruta más corta entre cada par de vértices. Inicialmente,dist[i][j]se establece en el peso del borde directamente conectado en el gráfico. Si no hay un borde directamente conectado entre i y j, entonces.dist[i][j]Establecer en infinito (lo que indica inalcanzable).

1. inicialización : Cree una matriz D de n × n, donde D [i] [j] se inicializa con el peso del borde directo de i a j en el gráfico, o se establece en infinito si no hay un borde directo entre i y j. Elemento diagonal D[i][i] = 0.

2. programación dinámica : Para cada vértice k (como vértice intermedio), actualice el camino más corto entre cada par de vértices i y j. Es posible obtener un camino más corto con k como punto intermedio. La fórmula de actualización es: D[i][j] = min(D[i][j], D[i][k] + D[k][j]). Esto significa que si el camino de i a j se acorta a través de k como vértice intermedio, actualice D[i][j].

3. Salida de resultados: Después de n rondas de iteraciones, cada elemento D [i] [j] en la matriz D es la longitud de camino más corta de i a j.

AcWing 343. Clasificación

Descripción de la pregunta

343. Clasificación - Banco de preguntas AcWing

Ejecutar código

#include <algorithm>
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
#define PII pair<int, int>
#define fi first
#define se second
#define endl 'n'
map<int, int> mp;
 
const int N = 210, mod = 1e9 + 7;
int T, n, m, k;
int a[N], dist[N][N];
PII ans[N];
 
void floyd(int x) // 以 x 为中转点，更新其他点。
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
}
 
bool pd() // 判断是否所有点都已确定
{
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 1; j <= n; j++)
            if (dist[i][j] != 1e9)
                cnt++; // 当前点能到达的点数
        ans[i] = {cnt, i};
        for (int j = 1; j <= n; j++)
            if (i != j && dist[j][i] != 1e9)
                cnt++; // 能到达当前点的点数
        if (cnt != n)
            return 0;
    }
    sort(ans + 1, ans + n + 1);
    return 1;
}
 
int main() {
    while (cin >> n >> m && n) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i != j)
                    dist[i][j] = 1e9;
 
        int flag = 0;
        for (int i = 1; i <= m; i++) {
            char a, t, b;
            cin >> a >> t >> b;
            int x = a - 'A' + 1, y = b - 'A' + 1; // 现在要加一条从 y 到 x 的边
 
            if (!flag && dist[x][y] != 1e9) // 发现已经从x能到y，出现矛盾
            {
                printf("Inconsistency found after %d relations.n", i);
                flag = 1;
            }
 
            dist[y][x] = 1;
            floyd(x), floyd(y); // 分别以 x 和 y 为中转点更新其他点
            if (!flag && pd()) { // 发现所有点都已确定
                printf("Sorted sequence determined after %d relations: ", i);
                for (int i = 1; i <= n; i++)
                    cout << char(ans[i].se + 'A' - 1);
                printf(".n");
                flag = 1;
            }
        }
        if (!flag)
            printf("Sorted sequence cannot be determined.n"); // 无法确定
    }
 
    return 0;
}

Ideas de código

1. inicialización: usar unadistLa matriz bidimensional se inicializa al infinito, lo que significa que no existe una relación de orden definida entre las desigualdades de forma predeterminada.
2. Leer entrada: Lea la relación de la entrada estándar en el formato "B > A", lo que indica que B es mejor que A.
3. Procesamiento de relaciones:
   • Cuando se lee una nueva relación, se comprueba si existe alguna contradicción (es decir, una relación previamente determinada entra en conflicto con la nueva relación).
   • renovardistMatrix, utilizando el algoritmo de Floyd para actualizar el camino más corto entre todas las desigualdades, aquí en realidad está actualizando la relación de "prioridad" u "orden".
4. Comprobar la seguridad de clasificación:
   • Compruebe que todas las desigualdades estén relacionadas, es decir, que cada punto pueda alcanzar cualquier otro punto y que la longitud del camino no sea infinita.
   • Si la clasificación se encuentra durante el proceso de lectura de la relación, o la clasificación aún no se puede determinar después de leer todas las relaciones, se generará la información correspondiente.

Mejorar ideas

• Mejora de la eficiencia : La llamada de Floyd actual se realiza inmediatamente después de agregar cada nueva relación, lo que puede no ser necesario. Puede esperar hasta que se hayan leído todas las relaciones antes de volver a realizar el algoritmo de Floyd para reducir cálculos innecesarios.
• Simplifica la lógica : El código actual es más complejo a la hora de detectar contradicciones y determinar la lógica de finalización de la clasificación. Puede intentar simplificar la lógica, como utilizar estructuras de datos más intuitivas o pasos algorítmicos para verificar estas condiciones.
• claridad del código: Puede aumentar la claridad de los comentarios y la estructura del código, haciendo que el código sea más fácil de entender y mantener.