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 dirigido y con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
ALGORITMO
Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.
1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi.
4. Si la distancia desde x hasta vi guardada en D es mayor que la distancia desde x hasta a sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada, esto es:
si (Di > Da + d(a, vi)) entonces Di = Da + d(a, vi)
5. Marcamos como completo el nodo a.
6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.
Una vez terminado al algoritmo, D estará completamente lleno.
¿ Para que es útil?
Muchas veces en la vida diaria queremos encontrar el camino mas eficiente para llegar a nuestro destino, este algoritmo es perfecto, ya que, evalúa todas las posibles rutas y escoje las mas corta para llegar al destino. Ciendo así la ruta mas eficiente. Ahora comparado con mi carrera es sumamente util, ya que hacer un programa que resuelva el problema en el menor tiempo, es el mejor. Poniendolo de otra forma, tu seras contratado, no el.
Calcular el camino mas corto de "1" a cualquier nodo
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,
ResponderEliminarBueno la verdad si me ah quedado muy claro el para que funciona,
me gustaría aclarar una duda, en la segunda imagen que colocaste, los nunmeros en color verde ¿me podrías aclarar que es lo que representan?
me doy a la idea de que son los lugares visitados por cada vertice pero no estoy del todo seguro.
agreadeceria me aclares la duda.
Un ejemplo de la vida diaria relacionado con ingenieria de este algoritmo es el que usan las companias de redes de comunicacion para distribuir eficientemente su cableado en donde se involucran un conjunto de nodos conectados mediante arcos, que transfiere vehículos desde determinados nodos origen a otros nodos destino, encontrando el camino mas corto para poder distribuir el cableado ayuda a que la compania ahorre tiempo y dinero.
ResponderEliminarTampoco me quedo muy claro lo de la segunda imagen si se esta calculando el camino mas corto del 1, Que representan los numeros verdes 2 y 3?. El 3 es el mas corto y por eso se detuvo ahi? si puedes responder gracias saludos..