Definicion DEL Algoritmo Dijkstra PDF

Preview

Summary

si esta completa las definiciones del algoritmo de dijkstra muchas gracias por ver el documento ...................................................................................................................................................

Description

DEFINICION DEL ALGORITMO DIJKSTRA El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado 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

El algoritmo de Dijkstra en cada paso selecciona un vértice “v” cuya distancia es desconocida, entre los que tiene la distancia más corta al vértice origen “s”, entonces el camino más corto de “s” a “v” ya es conocido y marca el vértice “v” como ya conocido. Así, sucesivamente se van marcando nuevos vértices hasta que estén todos marcados; en ese momento es conocida la distancia mínima del origen “s” al resto de los vértices. Entre las condiciones más importantes que deben considerarse para aplicar el algoritmo están: Las aristas deben tener un peso no negativo. El grafo debe ser dirigido y por supuesto ponderado.

CAMINO MAS CORTO. Una vez que se labora con grafos dirigidos etiquetados o ponderados con componentes de peso no negativos, es recurrente buscar el camino más corto entre 2 vértices dados; o sea, el camino que nos posibilite llegar a partir de un vértice origen a un vértice destino recorriendo la menor distancia o con el menor precio. Los algoritmos más utilizados para este fin son: Dijkstra, Floyd y Warshall. Los 3 algoritmos usan una matriz de adyacencia ponderada o etiquetada: que es la misma matriz de adyacencia usada para representar grafos, empero con la diferencia que en vez de situar un número “1” una vez que 2 vértices son adyacentes, se sitúa el peso o ponderación asignado a la arista que los une.

DISTANCIA O MATRICES DE COSTOS. El problema de buscar un camino más corto entre 2 nodos dados se puede solucionar por medio de un algoritmo voraz conocido como Algoritmo de Dijkstra.

ALGORITMO DEL CAMINO MAS CORTO O RUTA MAS CORTA (ALGORITMO DIJKSTRA)

El algoritmo de Dijkstra es un algoritmo eficiente (de dificultad O (n2), donde “n” es el número de vértices) que sirve para hallar el camino de coste mínimo a partir de un nodo origen a todos los otros nodos del grafo. Ha sido diseñado por el holandés Edsger Wybe Dijkstra en 1959. Este algoritmo es un típico ejemplo de algoritmo ávido, que resuelve los inconvenientes en sucesivos pasos, seleccionando en cada paso la solución más óptima para solucionar el problema. El motivo sobre el que se inspira este algoritmo es el inicio de optimizar: si el camino más corto entre los vértices “u” y “v” pasa por el vértice “w”, entonces la porción del camino que va de “w” a “v” debería ser el camino más corto entre todos los senderos que van de “w” a “v”. De esta forma, se van creando sucesivamente los senderos de coste mínimo a partir de un vértice inicial hasta todos los vértices del grafo, y se usan los senderos logrados como parte de los nuevos senderos....