Lugar y fecha de nacimiento: Rotterdam, Paises Bajos, 11 de mayo de 1930
Estudios: Dijkstra estudió física teórica en la Universidad de Leiden.
Trabajos: Trabajó como investigador para Burroughs Corporation a principios de los años 1970. En la Universidad de Texas en Austin, Estados Unidos, ocupó el Schlumberger Centennial Chair in Computer Sciences. Se retiró en 2000.
Conocido por: Entre sus contribuciones a la informática está la solución del problema del camino más corto, también conocido como el algoritmo de Dijkstra, la notación polaca inversa y el relacionado algoritmo shunting yard, THE multiprogramming system, el algoritmo del banquero y la construcción del semáforo para coordinar múltiples procesadores y programas. Otro concepto debido a Dijkstra, en el campo de la computación distribuida, es el de la auto-estabilización, una vía alternativa para garantizar la confiabilidad del sistema.
Lugar y fecha de muerte: Países Bajos, 6 de agosto de 2002
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 costos en cada arista.
El algoritmo de dijkstra determina la ruta más corta desde un nodo origen s hacia los demás nodos, las distancias se almacenan en un vector D. Básicamente, el algoritmo toma en la i-ésima iteración al nodo que tiene la menor distancia, Vi, y ve si es posible disminuir la distancia de sus nodos adyacentes, para hacerlo se verifica si la distancia hasta Vi más el costo para ir de i al nodo adyacente, w(i,j), es menor a la distancia actual en el nodo adyacente.
Referencias
No hay comentarios:
Publicar un comentario