1.ALGORITMO DE DIJKSTRA:
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más cortodado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de coste negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).
2. ALGORITMO DE FORD - FULKERSON :
El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo. Es aplicable a los Flujos maximales. La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino. Su nombre viene dado por sus creadores, L. R. Ford, Jr. y D. R. Fulkerson.
ANEXO: http://www.youtube.com/watch?v=bu1BnW9H9V0
3. CPM Y PERT :
Los métodos CPM (método de la ruta crítica o del camino crítico, critical path method) y PERT (técnica de evaluación y revisión de programa, program evaluation and review technique) se basa en redes, y tienen por objetivo auxiliar en la planeación, programación y control de proyectos. Se define un proyecto como conjunto de actividades interrelacionadas, en la que cada actividad consume tiempo y recursos. El objetivo del CPM y del PERT es contar con un método analítico para programar las actividadesANEXO : http://www.youtube.com/watch?v=8bR0WkJvfX0&feature=youtu.be
No hay comentarios:
Publicar un comentario