Instinto Lógico

Recuerda que nadie debe pensar por tí.

Etiqueta: El Frago

Dijkstra y el camino más corto

dijkstra_edgarEdsger Dijkstra (1930 -2002 ) es uno de los padres de la informática al que poca gente ajena a la informática conoce. Éste físico teórico realizó contribuciones fundamentales al campo de la informática actual están los semáforos, el algoritmo del banquero o la notación polaca inversa.

Todas las contribuciones mencionadas anteriormente han supuesto un avance significativo en el desarrollo informático, pero en esta entrada nos vamos a centrar en una de las contribuciones de Dijkstra que más se ha popularizado en los últimos tiempos gracias al uso de los GPS. Se trata del algoritmo que lleva su nombre: “El algoritmo de Dijkstra”.

El algoritmo de Dijkstra se aplica sobre un grafo ponderado y calcula la distancia desde un vértice inicial al resto de vértices del grafo. Los GPS tratan el mapa de carreteras como un grafo ponderado (cuyos pesos son o bien la distancia o el tiempo) y utilizan este algoritmo para calcular el camino más corto entre dos puntos.

Formulación del algoritmo de Dijkstra

Como se ha dicho anteriormente, el algoritmo de Dijkstra calcula la distancia desde un vértice inicial s al resto de vértices del grafo. En cada paso etiquetaremos los vértices del grafo de la siguiente forma: (dist(u),v), dónde dist(u) es la distancia acumulada desde el vértice s al u y v es el vértice predecesor de u en el camino más corto de s a u.

Para realizar el algoritmo de Dijkstra utilizaremos las siguientes estructuras: (más…)

Los maestros de nuestros padres

Don Bruno y Doña Angelita

“Digno Ayuntamiento de El Frago: Señoras y Señores. Voy a leeros mi trabajo, porque no podría dirigiros la palabra; Mis nervios se desatan y la emoción, subiendo a mi garganta, me impide continuar las ideas. Además quisiera deciros muchas cosas  ….”

Así comenzaba Carmen Romeo, parafraseando a doña Angelita, su conferencia el pasado sábado 9 de noviembre en El Frago.

Como dice un refrán popular: “Es de bien nacido ser agradecido”. Algo así debió de pensar Carmen Romeo cuando por casualidad se topó con Bruno Gracia Sieso y Ángela  García Alegre hace más de un año: Dos maestros y escritores con los que la historia, hasta ese momento, había sido ingrata. (más…)

Instinto Lógico © 2014 Frontier Theme