El algoritmo de Floyd-Warshall puede ser usado para resolver los
siguientes problemas, entre otros.
• Caminos corto en un grafo dirigido (Algoritmo
de Floyd)
• Clausura transitiva de grafos dirigidos
(Algoritmo de Warshall). En el algoritmo original de Warshal l, el grafo no tiene aristas con coste
o valor y es representado por una matriz Booleana de proximidad. Entonces la
operación de suma es remplazada por la aritmética Booleana “AND” y la operación
de mínimo es remplazada por “OR”.
• Búsqueda de
expresiones regulares dependiendo del lenguaje regular aceptado por una
autómata finito (Algoritmo de Kleene)
• Inversión de
matrices de números reales (Algoritmo de Gauss-Jordán)
• Planeamiento óptimo de
rutas. En esta aplicación uno está
interesado en encontrar la ruta con el máximo tráfico
entre dos vértices. Esto significa que, en vez de tomar el mínimo,
en su lugar uno toma el máximo. El coste de arista representa la constante de
flujo. Los
costes de caminos representan cuellos de botella; así
que la operación de adición es reemplazada por
la operación de mínimo.
• Probar si un grafo indirecto es bipartito (Un
Grafo bipartito se denomina en Teoría de grafos a un grafo cuyos vértices se
pueden separar en dos conjuntos disjuntos V1 y V2 y las aristas siempre unen
vértices de un conjunto con vértices de otro).
• Calculo rápido de redes de organización de
datos.
• Caminos de máximo ancho de banda.
No hay comentarios:
Publicar un comentario