ALGORITMO DE DIJKSTRA

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 corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista.

Este 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. 

Características del algoritmo

·         Es un algoritmo greddy.

·         Trabaja por etapas, y toma en cada etapa la mejor solución sin considerar consecuencias futuras.

·         El óptimo encontrado en una etapa puede modificarse posteriormente si surge una solución mejor.

Pasos del algoritmo

·         Sea V un conjunto de vértices de un grafo.

·         Sea C una matriz de costos de las aristas del grafo, donde en C[u,v] se almacena el costo de la arista entre u y v.

·         Sea S un conjunto que contendrá los vértices para los cuales ya se tiene determinado el camino mínimo.

·         Sea D un arreglo unidimensional tal que D[v] es el costo del camino mínimo del vértice origen al vértice v.

·         Sea P un arreglo unidimensional tal que P[v] es el vértice predecesor de v en el camino mínimo que se tiene construido.

·         Sea vinicial el vértice origen. Recordar que el Algoritmo Dijkstra determina los caminos mínimos que existen partiendo de un vértice origen al resto de los vértices.