Algortimo de Warshall
Páginas: 3 (609 palabras)
Publicado: 19 de marzo de 2013
ALGORITMO DE WARSHALL
ESTRUCTURAS AVANZADAS
El algoritmo de Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo engrafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución. El algoritmo de Warshall es un ejemplo de programación dinámicaCaracteristicas:
• Obtiene la mejor ruta entre todo par de nodos
• Trabaja con la matriz D inicializada con las distancias directas entre todo par de nodos
• La iteración se produce sobre nodos intermedios, esdecir, para todo elemento de la matriz se prueba si lo mejor para ir de i a j es a través de un nodo intermedio elegido o como estaba anteriormente, y esto se prueba con todos los nodos de la red .• Una vez probados todos los nodos de la red como nodos intermedios, la matriz resultante da la mejor distancia entre todo par de nodos
Ejemplo de camino mínimo entre todos los pares de nodosPara la ejecución de este algoritmo en Grafos no se requiere de la selección de ningún nodo origen o destino. Como su nombre indica, el algoritmo proporcionará todos los posibles caminosmínimos entre cada par de nodos origen y destino.
ALGORITMO DE WARSHALL
ESTRUCTURAS AVANZADAS
El algoritmo de Warshall, descrito en 1959 por Bernard Roy, es un algoritmo deanálisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución. El algoritmo de Warshalles un ejemplo de programación dinámica
Caracteristicas:
• Obtiene la mejor ruta entre todo par de nodos
• Trabaja con la matriz D inicializada con las distancias directas entre todo par denodos
• La iteración se produce sobre nodos intermedios, es decir, para todo elemento de la matriz se prueba si lo mejor para ir de i a j es a través de un nodo intermedio elegido o como estaba...
ESTRUCTURAS AVANZADAS
El algoritmo de Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo engrafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución. El algoritmo de Warshall es un ejemplo de programación dinámicaCaracteristicas:
• Obtiene la mejor ruta entre todo par de nodos
• Trabaja con la matriz D inicializada con las distancias directas entre todo par de nodos
• La iteración se produce sobre nodos intermedios, esdecir, para todo elemento de la matriz se prueba si lo mejor para ir de i a j es a través de un nodo intermedio elegido o como estaba anteriormente, y esto se prueba con todos los nodos de la red .• Una vez probados todos los nodos de la red como nodos intermedios, la matriz resultante da la mejor distancia entre todo par de nodos
Ejemplo de camino mínimo entre todos los pares de nodosPara la ejecución de este algoritmo en Grafos no se requiere de la selección de ningún nodo origen o destino. Como su nombre indica, el algoritmo proporcionará todos los posibles caminosmínimos entre cada par de nodos origen y destino.
ALGORITMO DE WARSHALL
ESTRUCTURAS AVANZADAS
El algoritmo de Warshall, descrito en 1959 por Bernard Roy, es un algoritmo deanálisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución. El algoritmo de Warshalles un ejemplo de programación dinámica
Caracteristicas:
• Obtiene la mejor ruta entre todo par de nodos
• Trabaja con la matriz D inicializada con las distancias directas entre todo par denodos
• La iteración se produce sobre nodos intermedios, es decir, para todo elemento de la matriz se prueba si lo mejor para ir de i a j es a través de un nodo intermedio elegido o como estaba...
Leer documento completo
Regístrate para leer el documento completo.