Algoritmo De Dijkstra

Algoritmo de Dijkstra
Alex Gutierrez#, Carolina Herrera*, Martin Bedon#
#Electronica y Telecomunicaciones, Universidad Peruana de Ciencias Aplicadas
1u920154@upc.edu.pe
3u920527@upc.edu.pe2u201011784@upc.edu.pe

Abstract— This document describes the Dijkstra Algorithm used to find the shortest path in the simulation of a city for the project of Computer Programming course, Pseudo GPS fora mobile car. The algorithm uses a graph of 34 vertices with weight between the vertices.

Keywords— optimalidad, grafo, vertices, costo minimo.
Introduccion
La lógica del algoritmo de Dijkstrase basa en hallar la ruta más corta entre los vértices de un grafo. Este algoritmo también es conocido como la solución al camino más corto. El algoritmo será muy útil en el proyecto del seudo GPS,porque ayudara a buscar la ruta más accesible al destino para evitar ir por el camino que le tome más tiempo. De algún modo, volverá al carrito a tomar decisiones gracias a este algoritmo.
ConceptoEl conocido algoritmo de Dijkstra, como se mencionó antes, permite hallar la ruta más corta entre los vértices de un grafo cuyas conexiones poseen una serie de pesos, se define que el camino de costomínimo de un vértice ‘a’ a otro ‘b’. La ruta elegida será el camino en el que la suma de los pesos de las conexiones que lo conforman es la más baja entre las de todos los caminos posibles entre ambosvértices. Este algoritmo fue diseñado por el holandés Edsger Dijkstra en 1959. Dicho algoritmo posee una complejidad de O(n2), siendo n el número de vértices; es un algoritmo eficiente, el cual sirvepara que se pueda encontrar el camino más corto entre un nodo y los demás nodos del grafo.

Fig. 1 Ejemplo de un grafo y de como posiciona los pesos.

A. Principio deOptimalidad
El fundamento base de este algoritmo es el principio de Optimalidad de Bellman, el cual se enuncia de esta forma: "Dada una secuencia óptima de decisiones, toda sub-secuencia de ella es, a...