Floyd-Warshall
Páginas: 2 (495 palabras)
Publicado: 9 de junio de 2013
Introducción
El algoritmo de Floyd-Warshall, permite hallar la ruta más corta en grafos dirigidos ponderados. Esté algoritmo a diferencia delalgoritmo de Dijkstra, no halla la distancias más cortas de un vértice fijo, sino todos los pares de distancias más cortas.
Ejemplo de Grafo Ponderado:
Algoritmos similaresLos algoritmos que se asimilan al algoritmo de Floyd - Warshall:
Algoritmo de Dijkstra, resuelve el problema de los caminos más cortos entre dos vértices, desde un origen y un único destino.Algoritmo de Bellman - Ford, resuelve el problema de los caminos más cortos desde un origen si la ponderación de las aristas es negativa.
Algoritmo de Búsqueda A*, resuelve el problema de loscaminos más cortos entre un par de vértices usando la heurística para intentar agilizar la búsqueda.
Algoritmo de Johnson, resuelve el problema de los caminos más cortos entre todos los vértices y puedeser más rápido que el de Floyd - Warshall en grafos de baja densidad.
Teoría perturbacional, encuentra en el peor de los casos el camino más corto a nivel local.
Algoritmo de Floyd-WarshallAlgoritmo de Floyd: Busca la distancia más corta entre 2 nodos dentro de un grafo.
Algoritmo de Warshall: Busca si están conectados entre sí los 2 nodos buscados.
En informática, el algoritmo deFloyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todoslos pares de vértices en una única ejecución. El algoritmo de Floyd-Warshall es un ejemplo de programación dinámica
Programación dinámica: Es un método para reducir el tiempo de ejecución deun algoritmo mediante la utilización de sub-problemas superpuestos y subestructuras óptimas.
El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices....
Introducción
El algoritmo de Floyd-Warshall, permite hallar la ruta más corta en grafos dirigidos ponderados. Esté algoritmo a diferencia delalgoritmo de Dijkstra, no halla la distancias más cortas de un vértice fijo, sino todos los pares de distancias más cortas.
Ejemplo de Grafo Ponderado:
Algoritmos similaresLos algoritmos que se asimilan al algoritmo de Floyd - Warshall:
Algoritmo de Dijkstra, resuelve el problema de los caminos más cortos entre dos vértices, desde un origen y un único destino.Algoritmo de Bellman - Ford, resuelve el problema de los caminos más cortos desde un origen si la ponderación de las aristas es negativa.
Algoritmo de Búsqueda A*, resuelve el problema de loscaminos más cortos entre un par de vértices usando la heurística para intentar agilizar la búsqueda.
Algoritmo de Johnson, resuelve el problema de los caminos más cortos entre todos los vértices y puedeser más rápido que el de Floyd - Warshall en grafos de baja densidad.
Teoría perturbacional, encuentra en el peor de los casos el camino más corto a nivel local.
Algoritmo de Floyd-WarshallAlgoritmo de Floyd: Busca la distancia más corta entre 2 nodos dentro de un grafo.
Algoritmo de Warshall: Busca si están conectados entre sí los 2 nodos buscados.
En informática, el algoritmo deFloyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todoslos pares de vértices en una única ejecución. El algoritmo de Floyd-Warshall es un ejemplo de programación dinámica
Programación dinámica: Es un método para reducir el tiempo de ejecución deun algoritmo mediante la utilización de sub-problemas superpuestos y subestructuras óptimas.
El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices....
Leer documento completo
Regístrate para leer el documento completo.