dijsktra

HISTORIA
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. Asu 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 dematrimonio 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, sele ofreció un puesto en Ciencias de la Computación en la Universidad de Texas, donde permaneció desde entonces hasta que recientemente el 6 Agosto del 2002, Edsger W. Dijkstra, Professor Emeritus of Computer Sciences and Mathematics at The University of Texas en Austin, falleció en su hogar de Nuenen, (Netherlands). Es miembro honorario de la Academia Americana de Artes y Ciencias y de RealAcademia 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
ALGORITMO DE DIJKSTRA (RUTA MÁS CORTA - ÁRBOL MÍNIMO - CAMINO MÍNIMO)
En 1956, Dijkstra anunció su algoritmo de caminos mínimos, después de haber estado trabajando con el ARMAC, el ordenador que el CentroMatemá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
Unared 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 algoritmode 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 maneramás general, la longitud de un enlace puede depender de su capacidad de transmisión y su carga de tráfico
Djikstra quería estudiar Derecho y asi poder representar a los Paises Bajos en las Naciones Unidas. Pero, en 1948 realizó los exámenes finales de su etapa en la escuela secundaria y sacó notas excelentes en matematicas, física, química y biología, y tanto sus padres como sus profesores...