Finanzas y Contabilidad

Algoritmo de Dijkstra

1. Introducción
2. Desarrollo del tema
a) Definición
b) El creador
c) Descripción del algoritmo
d) Aplicaciones
e) Otros algoritmos similares
3. Conclusión

Actualmente hay mucha gente que utiliza aplicaciones como Google Maps
o el Tom Tom para determinar la ruta más óptima y corta entre dos lugares.
Seguramente que a alguien, aparte de mí, se le ha ocurrido lapregunta ¿ por
qué estas aplicaciones son capaces de hacerlo?. Así pues el motivo y el objetivo
principal de este trabajo es desvelar el fundamento en que está basado dichas
aplicaciones, lo cual nos conduce hasta el algoritmo de Dijkstra.
El algoritmo de Dijkstra es un mecanismo formado por una serie de
razonamientos lógicos que nos permite determinar el camino más corto (de ahí
quetambién sea conocido como “algoritmo de caminos mínimos”) dado un
punto de origen al resto de puntos en un grafo (mapa formado por vértices y
aristas) con peso (valor) no negativo en cada arista.
Este algoritmo fue creado por Edsger Wybe Dijkstra (de ahí viene el
nombre), quien lo concibió en 1956 y ha perdurado hasta nuestros días.
Dijkstra fue un científico de la computación de los Países Bajos yes muy
conocido en el campo de las ciencias informáticas debido a sus aportaciones
técnicos como los algoritmos sobre grafos y semáforos. También es destacado
por sus opiniones acerca de la programación como disciplina matemática.
Obtuvo varios premio por sus trabajos, entre ellos, el más famoso fue el del
Turing, un premio de las ciencias de la computación que se otorga anualmente
a quieneshayan contribuido de manera trascendental al campo de las ciencias
computacionales.
En cuanto a la estrategia del algoritmo, la idea consiste en ir explorando
todos los caminos y establecer el más corto. Para ello, debemos partir de un
grafo ponderado, es decir, un mapa formado por vértices y aristas con peso
positivo en las aristas.

En primer lugar, lo que hace el algoritmo esseleccionar un vértice de
origen. Luego hacemos una tabla con todos los vértices del grafo estableciendo
las distancias del vértice de origen al resto en infinito, ya que es la máxima
distancia que puede haber, pues son desconocidas en un principio.
En segundo lugar, recorreremos los vértices adyacentes (dos vértices son
adyacentes si están unidos por una arista) al del origen y analizamos si lasdistancias guadadas (que en el principio son infinito) son superiores al peso de
las aristas que las unen, en caso contrario (que debe serlo en este paso), las
distancias guardadas (infinito) se sustituye por ésta última, al ser inferior. Al
terminar este paso, se marca el vértice cuya distancia es la menor entre las
demás junto con la arista, pues ya se ha establecido el camino y la distanciamínima desde este vértice al origen.
Posteriormente, repetimos este proceso de análisis añadiendo nuevos
vértice, es decir, los adyacentes del vértice ya marcado, cuya distancia se
calcula sumando el peso de la arista que une el nuevo vértice con el ya marcado
más el peso de la arista entre el vértice ya marcado y el del origen. Sustituimos
las distancias guardadas por la menor y volvemos amarcamos el vértice de
menor distancia junto con la arista que le conduce hasta el origen.
De esta manera, se repite este proceso de incorporación y actualización de
las distancias para el resto de vértices hasta que todos estén marcados.
Entonces habremos terminado el algoritmo estableciendo el camino mínimo
desde el vértice de origen hasta todos los demás vértices del grafo.
Así pues, todoeste proceso del algoritmo es traducido al lenguaje
informático e implementado en los programas para poder poner en práctica su
utilidad. Por ejemplo, se usa bastante en redes de computadores, donde los
vértices corresponden a los routers y las aristas entre ellos, las conexiones. A
cada conexión se le asigna un distancia y de esta forma algunos protocolos de
enrutamiento podrá usar el...