Informe Dijkstra 5u1i67

UNIVERSIDAD CENTRAL DEL ECUADOR FACULTAD DE INGENIERÍA CIENCIAS FÍSICAS Y MATEMÁTICAS INGENIERÍA EN INFORMÁTICA INFORME DE ALGORITMOS Integrantes: Oliver Sánchez, Isaac Hernández, Jamil Arellano Curso: 3ro Ing. Informática

Fecha:7 de febrero del 2018

Tema: Algoritmo de Dijkstra.

Objetivo General Implementar el algoritmo de Dijkstra en un programa capaz de encontrar el camino más corto entre dos vértices pertenecientes a un grafo. Objetivos Específicos  

Comprender los beneficios e importancia del algoritmo de Dijkstra en la solución de grafos, en relación al camino de coste mínimo de un vértice a otro. Implementar una interfaz gráfica al programa que sea amigable con el . Descripción del Proyecto

Comprender de una forma más clara el funcionamiento y aplicación del algoritmo de Dijkstra e implementar el algoritmo para proporcionar la forma más optima de encontrar el camino más corto entre los vértices de un grafo, además se añadirá interfaz gráfica con las opciones de: insertar nodo, eliminar nodo, insertar y eliminar arista, agregar peso, grafo dirigido y Dijkstra. Para que el programa sea más fácil y comprensible al utilizarlo. Algoritmo de Dijkstra se define el camino de coste mínimo de un vértice u a otro v, como el camino donde la suma de los pesos de los arcos que lo forman es la más baja entre las de todos los caminos posibles de u a v. El algoritmo de Dijkstra es un algoritmo eficiente (de complejidad 𝑂(𝑛2 ) donde n es el número de vértices) que sirve para encontrar el camino de coste mínimo desde un nodo origen a todos los demás nodos del grafo. Fue diseñado por el holandés Edsger Wybe Dijkstra en 1959.El fundamento sobre el que se asienta este algoritmo es el principio de optimalidad. (Terrazas) Infraestructura del Computador

Sistema operativo: Windows 10 Procesador: Intel core i5 6ta generación Memoria RAM: 8GB Tipo de sistema: sistema operativo de 64bits Capacidad de disco: 1TB Alcance del Proyecto Al realizar el programa planteado aplicamos los conocimientos adquiridos acerca de la teoría de grafos y el algoritmo de Dijkstra con el fin de relacionar ambas partes en una interfaz gráfica y fácil de manejar por el . Limitaciones Este programa requiere de tres bibliotecas para su correcta ejecución las cuales son: gs-core, gs-algo, gs-ui. Estas bibliotecas se las puede descargar directamente de la página web: http://graphstream-project.org//. Conclusiones y Recomendaciones Conclusiones Se logró analizar el algoritmo de Dijkstra y entender cómo funciona. Se logró implementar el algoritmo de Dijkstra en una interfaz gráfica relacionada al tema de grafos. Recomendaciones Se recomienda instalar las tres bibliotecas mencionadas anteriormente para una buena ejecución y funcionamiento del programa.

Referencias: Terrazas, G. S. (s.f.). Obtenido de http://bioinfo.uib.es/~joemiro/aenui/procJenui/ProcWeb/actas2001/saalg223.pdf

Firma de integrantes:

Jamil Arellano

Isaac Hernández

Oliver Sánchez Estrada