Instinto Lógico

Recuerda que nadie debe pensar por tí.

Etiqueta: recorrido

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…)

Euler: Los puentes de Konigsberg y la teoría de grafos

En matemáticas ocurre con cierta frecuencia que acertijos, paradojas y problemas en apariencia intranscendentes han dado paso teorías y resultados de gran transcendencia y  profundidad. Este es el caso del la curiosidad que despertó el problema del paseo por los puentes de Konigsberg (actual Kaliningrado) que traía de cabeza a muchos de sus habitantes sin dejar de ser una curiosidad que no iba más allá de chascarrillos de paseantes y que cuando se ocupó de él Leonard Euler (1707-1783) y lo trató de forma matemática dio lugar a una nueva rama de las matemáticas que se conoce como teoría de grafos.

Con teoría de grafos se resuelven problemas de estrategias de juegos, de cálculo de rutas óptimas, así como su aplicación a las cuestiones más diversas como optimización en la logística, la robótica, la genética, la sociología o el diseño de redes.

El problema

El problema que dio origen a la teoría de grafos era, como hemos señalado, el paseo atravesando los siete puentes sobre el río Pregel. Este río tenía una isla, isla de Kneiphof, en medio  a la que llegaban cinco puentes, dos a cada orilla y otro que llevaba a otra isla dentro del río, que, a su vez estaba unida a las orillas por sendos puentes, tal y como indica la figura siguiente:

 Puentes de Konigsberg

(más…)

Instinto Lógico © 2014 Frontier Theme