Algoritmo de Edsger Dijkstra

Edsger Wybe Dijkstra nació en Rotterdam, (Holanda) en 1930. Sus padres eran ambos intelectuales y él recibió una excelente educación. Su padre era químico y su madre matemática. En 1942, cuando Dijkstra tenía 12 años, entró en Gymnasium Erasminium, una escuela para estudiantes especialmente brillantes, donde dio clases, fundamentalmente, de Griego, Latín, Francés, Alemán, Inglés, biología, matemáticas y química. En 1945, Dijkstra pensó estudiar Derecho y trabajar como representante de Holanda en las Naciones Unidas.

Sin embargo, debido a su facilidad para la química, las matemáticas y la física, entró en la Universidad de Leiden, donde decidió estudiar física teórica. Durante el verano de 1951, asistió a un curso de verano sobre programación en la Universidad de Cambridge. A su vuelta empezó a trabajar en el Centro Matemático en Amsterdam, en marzo de 1952, donde se incrementó su creciente interés en la programación. Cuando terminó la carrera se dedicó a problemas relacionados con la programación. Pero uno de los problemas con que se encontró es que ser programador no estaba oficialmente reconocido como una profesión. De hecho, cuando solicitó una licencia de matrimonio en 1957, tuvo que señalar que su profesión era físico teórico.

Dijkstra continuó trabajando en el Centro Matemático hasta que aceptó un trabajo como desarrollador en Burroughs Corporation, en los Estados Unidos, a principio de la década de los 70. En 1972 ganó el Premio Turing ACM, y ,en 1974, el AFIPS Harry Good Memorial. Dijkstra se trasladó a Austin, Texas a principio de los 80. En 1984, se le ofreció un puesto en Ciencias de la Computación en la Universidad de Texas, donde ha permanecido desde entonces. Es miembro honorario de la Academia Americana de Artes y Ciencias y de Real Academia Holandesa de Artes y Ciencias. Además es miembro distinguido de la Sociedad de Computación Británica. Finalmente es Doctor Honoris Causa en Ciencias por la Queen’s University Belfast.

En 1956, Dijkstra anunció su algoritmo( Una posible definición de algoritmo es un conjunto de reglas que permiten obtener un resultado determinado apartir de ciertas reglas definidas. Otra definición sería, algoritmo es una secuencia finita de instrucciones, cada una de las cuales tiene un significado preciso y puede ejecutarse con una cantidad finita de esfuerzo en un tiempo finito. Ha de tener las siguientes características: legible, correcto, modular, eficiente, estructurado, no ambiguo y a ser posible se ha de desarrollar en el menor tiempo posible.) algoritmo de caminos mínimos, después de haber estado trabajando con el ARMAC, el ordenador que el Centro Matemático poseía. Más tarde propuso el algoritmo del árbol generador minimal. A principios de la década de los 60, Dijkstra aplicó la idea de la exclusión mutua a las comunicaciones entre una computadora y su teclado.Su solución de exclusión mutua ha sido usada por muchos procesadores modernos y tarjetas de memoria desde 1964, cuando IBM la utilizó por primera vez en la arquitectura del IBM 360. El siguiente problema del que se ocupó Dijkstra fue el de los filósofos comensales. En este problema, cinco filósofos están sentados en una mesa circular con un plato de arroz delante y un palillo a cada lado, de manera que hay cinco palillos en total. El problema trata sobre el uso de recursos comunes sin que los procesos (los filósofos) lleguen a una situación de bloqueo mutuo, inanición y que los recursos sean usados de la manera más eficiente por todos los procesos. También ayudó a fomentar la disciplina en la programación: “GOTO se puede considerar dañino. Cuanto más sentencias GOTO haya en un programa, más difícil es entender el código fuente”.

El problema de la ruta más corta se puede resolver utilizando programación lineal sin embargo, debido a que el método simplex es de complejidad exponencial, se prefiere utilizar algoritmos que aprovechen la estrutura en red que se tiene para estos problemas.

Una red de comunicaciones involucra un conjunto de nodos conectadas mediante arcos, que transfiere vehículos desde determinados nodos origen a otros nodos destino. La forma más común para seleccionar la trayectoria (o ruta) de dichos vehículos, se basa en la formulación de la ruta más corta. En particular a cada arco se le asigna un escalar positivo el cual se puede ver como su longitud.

Un algoritmo de trayectoria más corta, rutea cada vehículo a lo largo de la trayectoria de longitud mínima (ruta más corta) entre los nodos origen y destino. Hay varias formas posibles de seleccionar la longitud de los enlaces. La forma más simple es que cada enlace tenga una longitud unitaria, en cuyo caso, la trayectoria más corta es simplemente una trayectoria con el menor número de enlaces. De una manera más general, la longitud de un enlace puede depender de su capacidad de transmision y su carga de tráfico.
La solución es encontrar la trayectoria más corta. Esperando que dicha trayectoria contenga pocos enlaces no congestionados; de esta forma los enlaces menos congestionados son candidatos a pertenecer a la ruta. Hay algoritmos de ruteo especializados que también pueden permitir que la longitud de cada enlace cambie en el tiempo, dependiendo del nivel de tráfico de cada enlace. De esta forma un algoritmo de ruteo se debe adaptar a sobrecargas temporales y rutear paquetes alrededor de nodos congestionados. Dentro de este contexto, el algoritmo de ruta más corta para ruteo opera contínuamente, determinando la trayectoria más corta con longitudes que varían en el tiempo.
El algoritmo de Dijkstra para ruta más corta, en términos generales, encuentran la ruta más corta entre dos nodos, inicial a y final z, de la siguiente manera:

Los nodos de la red son etiquetados con números. Al principio, todos tienen la etiqueta 00 excepto el nodo inicial a que tiene la etiqueta 0. Los arcos tienen un peso wij que representa la distancia del enclace (i, j). El algoritmo de Dijkstra renumeran los nodos, de manera que cuando el nodo z tiene una etiqueta permanente, se ha obtenido la solución final.

Aqui la muestra del código fuente.

5 respuestas a Algoritmo de Edsger Dijkstra

  1. Jromero dice:

    Este algoritmo es uno de los mas eficaces y simplifica la tarea al momento de tratar de implmentar una solucion de la ruta mas corta, ya sea en programcion, o en redes de comunicaciones.
    Interesante artículo.

  2. robin dice:

    Si el algoritmo es bueno pero prefiero el solver,pero NO sabia que el arbol de expansion minima no tenia solucion en programacion lineal y me pasa un DIA webiando jajajajajajajajajaja pero ojo llegue a una solucion bastante cercana …jajaja

  3. Howdy, i read your blog from time to time and i own a similar one and i was just
    curious if you get a lot of spam responses? If so how do you reduce it,
    any plugin or anything you can suggest? I get so much lately
    it’s driving me crazy so any help is very much appreciated.

  4. Baldev Gara dice:

    It’s a pity you don’t have a donate button!
    I’d most certainly donate to this excellent blog! I guess for now i’ll settle for
    book-marking and adding your RSS feed to my Google account.
    I look forward to new updates and will share this blog with my Facebook group.

    Chat soon!

  5. weight loss dice:

    It may not have been more timely. After the incident seriously it could lead to more serious
    cases like cervical cancer for women or worse still HIV-AIDS.
    Knowing what is and is called WHODAT.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: