Instituto tecnológico superior de Alvarado

Ingeniería en sistemas computacionales

BHnandezA5.2

Cesar Triana Flores

Matemáticas discretas

Investigación:

Diferentes algoritmos para el cálculo del número de

caminos en un grafo, así como el camino más cortó

18/nov/2023

Semiescolarizado
 Índice

1. Portada
2. Hoja de presentación
3. Índice
4. Introducción
5. Objetivo
6. Algoritmo de Dijkstra
7. Camino mas corto
8. Algoritmo A-Estrella
9. Conclusión
10. Referencias
 Introducción
Existen numerosos problemas que se pueden formular en términos
de grafos. Ejemplos de ello son la planificación de las tareas que
completan un proyecto, encontrar las rutas de menor longitud entre dos
puntos geográficos, calcular el camino más rápido en un transporte,
determinar el flujo máximo que puede llegar desde una fuente a, por
ejemplo, una urbanización; entre otros. La resolución de estos problemas
requiere examinar todos los nodos o todas las aristas del grafo que
representa al problema; sin embargo, existen ocasiones en que la
estructura del problema es tal que sólo se necesitan visitar algunos de los
nodos o bien algunas de las aristas. Los algoritmos imponen
implícitamente un orden en estos recorridos: visitar el nodo más próximo o
las aristas más cortas, y así sucesivamente; otros algoritmos no requieren
ningún orden concreto en el recorrido.

Un grafo es una estructura de datos que almacena datos de dos

tipos:

• vértices o nudos, con un valor almacenado

• aristas o arcos: cada una conecta a un vértice con otro, y puede

tener un valor almacenado

- una arista es un par de vértices (v,w)

- si el par está ordenado, se dice que el grafo es dirigido o que es

un dígrafo.
 Objetivo

Los grafos, constituyen estructuras de datos en las que se pueden

expresar relaciones de conexión entre diversos elementos denominados
vértices. Cada conexión se representa por un dato llamado arista Los
grafos tienen gran cantidad de aplicaciones; por ejemplo:

• Representación de circuitos electrónicos analógicos y digitales

• Representación de caminos o rutas de transporte entre

localidades

• Representación de redes de computadores. Uno de los problemas

más importantes en los grafos es el de encontrar el camino de coste
mínimo.
 Algoritmo de Dijkstra

Este algoritmo fue creado por uno de los padres de la computación,

Edger W. Dijkstra, en 1956. Sirve para cualquier grafo con pesos (dirigido
o no) siempre y cuando sus pesos no sean negativos.

El algoritmo calcula las distancias mínimas desde un nodo inicial a

todos los demás. Para hacerlo, en cada paso se toma el nodo más
cercano al inicial que aún no fue visitado (le diremos v). Este nodo tiene
calculada la menor distancia al nodo inicial (¿por qué?).

Luego, recalculamos todas los caminos mínimos, teniendo en

cuenta a v como camino intermedio.

Así, en cada paso tendremos un subconjunto de nodos que ya

tienen calculada su mínima distancia y los demás tienen calculada su
mínima distancia si solo puedo usar los nodos del conjunto como nodos
intermedios.

Con cada iteración agregaremos un nodo más a nuestro conjunto,

hasta resolver el problema en su totalidad.
Camino más Corto.

Cuando se trabaja con grafos dirigidos etiquetados o ponderados

con factores de peso no negativos, es frecuente buscar el camino más
corto entre dos vértices dados; es decir, el camino que nos permita llegar
desde un vértice origen a un vértice destino recorriendo la menor distancia
o con el menor costo.

Los algoritmos más usados para este fin son: Dijkstra, Floyd y
Warshall.

Los tres algoritmos utilizan una matriz de adyacencia ponderada o

etiquetada: que es la misma matriz de adyacencia utilizada para
representar grafos, pero con la diferencia que en lugar de colocar un
número “1” cuando dos vértices son adyacentes, se coloca el peso o
ponderación asignado a la arista que los une.

Con frecuencia en la matriz etiquetada suele utilizarse la siguiente

notación:

Suponiendo que M [i, j] representa la matriz de adyacencia,

tenemos:

M [i, j] = 0, si i = j

M [i, j] = 1000 ó ∞, si no existe un camino de i a j, donde ij

M [i, j] = costo de ir del vértice i al vértice j

Otro nombre con el cual suele llamarse a una matriz de adyacencia

etiquetada es matriz de distancias o matriz de costos.

El problema de buscar un camino más corto entre dos nodos dados

se puede resolver mediante un algoritmo voraz conocido como Algoritmo
de Dijkstra.
 Algoritmo del camino más corto o ruta más corta (Algoritmo de
Dijkstra). El algoritmo de Dijkstra es un algoritmo eficiente (de complejidad
O (n2 ), 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.
Este algoritmo es un típico ejemplo de algoritmo ávido, que resuelve los
problemas en sucesivos pasos, seleccionando en cada paso la solución
más óptima con el objeto de resolver el problema.

El fundamento sobre el que se basa este algoritmo es el principio

de optimizar: si el camino más corto entre los vértices “u” y “v” pasa por el
vértice “w”, entonces la parte del camino que va de “w” a “v” debe ser el
camino más corto entre todos los caminos que van de “w” a “v”. De esta
manera, se van construyendo sucesivamente los caminos de coste
mínimo desde un vértice inicial hasta cada uno de los vértices del grafo, y
se utilizan los caminos conseguidos como parte de los nuevos caminos.

Dicho en otras palabras: “Dado un grafo a cuyos arcos se han

asociado una serie de pesos, 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 en cada paso selecciona un vértice “v” cuya
distancia es desconocida, entre los que tiene la distancia más corta al
vértice origen “s”, entonces el camino más corto de “s” a “v” ya es
conocido y marca el vértice “v” como ya conocido. Así, sucesivamente se
van marcando nuevos vértices hasta que estén todos marcados; en ese
momento es conocida la distancia mínima del origen “s” al resto de los
vértices.

Entre las condiciones más importantes que deben considerarse

para aplicar el algoritmo están:
  Las aristas deben tener un peso no negativo.
 El grafo debe ser dirigido y por supuesto ponderado.

Una posible aplicación de este algoritmo se presenta cuando se

desea encontrar la ruta más corta entre dos ciudades; cada vértice
representa una ciudad y las aristas representan la duración de los vuelos.

A continuación se presenta el algoritmo. Para la explicación general

se tomará como referencia los siguientes pasos:

1. Seleccionar vértice de partida, es decir un origen.

2. Marcar el punto de partida como el punto de inicio.

3. Determinar los caminos especiales desde el nodo de partida, es

decir, el de inicio.

4. Camino especial es aquel que solo puede trazarse a través de

los nodos o vértices ya marcados.

5. Para cada nodo no marcado, se debe determinar si es mejor usar

el camino especial antes calculado o si es mejor usar el nuevo camino
especial que resulte al marcar este nuevo nodo.

6. Para seleccionar un nuevo nodo no marcado como referencia,

deberá tomarse aquel cuyo camino especial para llegar a él es el mínimo,
por ejemplo si anteriormente marqué el nodo o vértice 2, el cual tiene dos
nodos adyacentes 3 y 4 cuyo peso en la arista corresponde a 10 y 5
respectivamente, se tomará como nuevo nodo de partida el 4, ya que el
peso de la arista o camino es menor.

7. Cada camino mínimo corresponde a la suma de los pesos de las

aristas que forman el camino para ir del nodo principal al resto de nodos,
pasando únicamente por caminos especiales, es decir nodos marcados.
 Algoritmo A-Estrella

Fue desarrollado en 1968 para combinar el enfoque heurístico del

algoritmo BFS, y el enfoque optimal del algoritmo de Dijkstra. Es el único
algoritmo heurístico, que garantiza que encuentra el camino mas corto
entre dos nodos dados. Este algoritmo es ampliamente utilizado en video
juegos, y en aplicaciones de inteligencia artificial, donde la velocidad de
respuesta es lo principal. Los juegos de video que más utilizan este
algoritmo son los de estrategia en tiempo real, en los cuales los
personajes deben desplazarse de un punto a otro por un mapa
determinado. También es utilizado para implementar la inteligencia
artificial de los oponentes controlados por el computador, el cual pede
tener en cuenta muchos aspectos, como la cercanía con los oponentes y
el rango de visión entre otros.

El algoritmo estrella funciona de la siguiente forma. Tiene dos

conjuntos de vértices, a uno de estos conjuntos lo vamos a llamar
disponibles, y al otro lo vamos a llamar analizados. En el conjunto
disponibles se colocan los nodos que son candidatos a ser examinados
para escoger el camino, y en el conjunto analizados están los nodos que
ya han sido examinados, y que hacen parte de la ruta seleccionada.
Inicialmente el conjunto disponibles contiene únicamente el nodo inicial, y
el conjunto analizados esta vacío.

El algoritmo A-Estrella a diferencia del Dijkstra, no siempre

encuentra el camino optimo, pero tampoco se desvía mucho de la
respuesta óptima. La precisión de este algoritmo depende totalmente de la
función heurística utilizada. Si la función heurística utilizada es igual a
cero, es decir no se utiliza heurística, el algoritmo A-Estrella es
exactamente igual al Dijkstra.
 Concusión

Un grafo es una estructura matemática que puede ser usada para

modelar redes y una gran cantidad de otros sistemas donde las relaciones
entre los objetos juegan un papel muy importante.

Esta compuesto por un conjunto de vértices y otro de arcos. Los

arcos unen un vértice con otro. El conjunto vértices se denota con “V”, y el
de arcos con “E”. Los grafos pueden ser dirigidos o no. Un grafo dirigido,
es uno en el cual los arcos solo tiene una dirección determinada, mientras
que uno no dirigido, los arcos tienen dirección en ambos sentidos. Un arco
puede tener un costo o impedancia asociado, el cual representa el costo
requerido de pasar de un vértice a otro vértice, utilizando dicho arco. Un
grafo esta denotado de la siguiente forma:

G= (V,E)

El algoritmo de Dijkstra encuentra el camino más corto entre un

nodo dado (el nodo de origen) y todos los otros nodos del grafo. Este
algoritmo usa los valores de los arcos para encontrar el camino que
minimiza el valor total entre el nodo de origen y los demás nodos del grafo.

Los algoritmos más importantes son:

Algoritmo de Dijkstra, resuelve el problema de los caminos más

cortos desde un único vértice origen hasta todos los otros vértices del
grafo.

Algoritmo de Bellman - Ford, resuelve el problema de los caminos

más cortos desde un origen si la ponderación de las aristas es negativa.

Algoritmo de Búsqueda A*, resuelve el problema de los caminos

más cortos entre un par de vértices usando la heurística para intentar
agilizar la búsqueda.
 Algoritmo de Floyd - Warshall, resuelve el problema de los caminos
más cortos entre todos los vértices.

Algoritmo de Johnson, resuelve el problema de los caminos más

cortos entre todos los vértices y puede ser más rápido que el de Floyd-
Warshall en grafos de baja densidad.

Algoritmo de Viterbi, resuelve el problema del camino estocástico

más corto con un peso probabilístico adicional en cada vértice.
 Referencias

Bibliografía
Castañeda, L. R. (Junio de 2005). Algoritmos para calcular la ruta mas corta .
Recuperado el 17 de Noviembre de 2023, de
https://repositorio.uniandes.edu.co/server/api/core/bitstreams/7a9e2cbc-
ac42-4812-8fc9-ac4f872b1527/content

Gonzalez, M. (4 de Noviembre de 2009). Estructuras de datos y algoritmos .

Recuperado el 17 de Noviembre de 2023, de
https://www.ctr.unican.es/asignaturas/eda/cap4-grafos-2en1.pdf

s/n. (12 de Octubre de 2016). Algoritmos para la ruta mas corta en un grafo.
Recuperado el 17 de Noviembre de 2023, de
https://www.udb.edu.sv/udb_files/recursos_guias/informatica-
ingenieria/programacion-iv/2019/ii/guia-10.pdf

Sclar, M. (2016). Camino minimo en grafos . Recuperado el 17 de Noviembre de

2023, de https://www.oia.unsam.edu.ar/wp-
content/uploads/2017/11/dijkstra-prim.pdf