Algoritmo de Dijkstra

Algoritmo de Dijkstra



I. ABSTRACT

En el presente documento explicaremos el uso y los beneficios del algoritmo de Dijkstra en un ambiente relativamente pequeño como es el campus de la Universidad Católica Boliviana, donde mostraremos el camino más óptimo a tomar entre bloque y bloque, además de mostrar lo fácil que es implementar este algoritmo a situaciones cotidianas.

II.INTRODUCCIÓN

Con el rápido crecimiento de la ciudad de La Paz, las distancias cada vez se hacen más grandes, además de la creciente cantidad de automóviles que están circulando hizo que el trafico sea bastante complicado en diferentes horas del día, lo cual hace que sea más complicado desplazarse de un de un punto de la ciudad a otro de forma óptima, habiendo muchos caminos posibles para elegir,
Eneste caso utilizamos a la Universidad Católica Boliviana como un ejemplo a un lugar potencial para implementar el algoritmo de Dijkstra, para reducir el número de atrasos registrados en los últimos meses, implementaremos este algoritmo para trazar rutas optimas entre los bloques de la Universidad Católica Boliviana, para un fácil recorrido de punta a punta en poco tiempo.
Este programa ademásincluirá una opción para mostrar el camino más largo posible de un punto a otro punto del campus, esto va dedicado para la gente que disfrute de una buena caminata o un buen ejercicio.


Plano Ucb La Paz

III. ANTECEDENTES

Este algoritmo fue utilizado previamente en Quito -Ecuador el año 2005 bajo el nombre de “Sistema de información geográfica para la distribución de productos noperecederos”, esta tesis está dirigida para solucionar un problema de la distribución de productos no perecederos constituyendo adicionalmente una herramienta de soporte para la toma de decisiones en otros departamentos de una empresa.
También fue utilizado este algoritmo en Universidad Tecnológica de Pereira – Colombia bajo el nombre de “Aplicación de la teoría de grafos y el algoritmo de dijkstra paradeterminar las distancias y las rutas más cortas en una ciudad” cuyo propósito era el de trazar rutas optimas entre diferentes puntos de la ciudad de Santa Rosa de Cabal.

IV. OBJETIVO GENERAL

Aplicar el algoritmo de dijkstra dentro de la Universidad Católica Boliviana “San Pablo” para poder hallar el camino más óptimo de un punto a otro viendo a donde se desea ir.

V. OBJETIVOS ESPECIFICOS

-Hacer un programa en donde se encuentren todos los bloques, garajes y centros de información de la Universidad Católica Boliviana “San Pablo”.
- Dar opciones al usuario para elegir, es decir, si desea una ruta ya sea corta o larga para poder desplazarse desde el punto en que se encuentra hasta donde desea ir.
- Poder guardar la información que nos proporcione el programa sobre la ruta máscorta o larga, para así poder disponer de ella posteriormente para otras situaciones.

VI. MARCO TEÓRICO

I. Primer Algoritmo de Dijkstra (Shortest Path)

El algoritmo de Dijkstra o algoritmo de caminos mínimos, fue el primer algoritmo diseñado por Edsger Dijkstra, sirve para determinar el camino más corto de un lugar a otro, o en este caso de un punto origen donde está el usuario hasta uno delos bloques a donde desea llegar de la Universidad Católica Boliviana “San Pablo”.

Teniendo un grafo de n nodos (vértices) se debe tener entre todos esos nodos un nodo origen (vértice origen), sin embargo cada vértice debe tener un peso (valor). Para poder resolver el Algoritmo de Dijkstra se debe tener un conjunto de vértices, V = {v1, v2, v3,….., vn} y P = (wij) n x n, que sería una matriz depesos de n x n y finalmente se requiere de un vértice inicial, vi. Ahora debemos crear una lista, Vu, en donde estén todos los vértices que ya tienen un camino más óptimo (corto o largo). Posteriormente, se debe crear un vector en donde se lleven los pesos mínimos, D.

El algoritmo de Dijkstra empieza a buscar desde el punto origen, vi, la ruta más óptima hasta los otros vértices, el...