Posgrado
  1. Introducción al análisis real  1.1. Teoría de conjuntos y lógica en el análisis real  1.1.1. Conjuntos y operaciones en teoría de conjuntos y lógica en análisis real  1.1.2. Relaciones y funciones  1.1.3. Lógica y cuantificadores  1.1.4. Cardinalidad de conjuntos  1.2. Espacio métrico  1.2.1. Introducción a conjuntos abiertos y cerrados en espacios métricos  1.2.2. Convergencia de secuencias en un espacio métrico  1.2.3. Función continua en un espacio métrico  1.2.4. Compacidad y completitud en espacios métricos en análisis real  1.3. Secuencias y series  1.3.1. Convergencia de secuencias  1.3.2. Series infinitas  1.3.3. Convergencia uniforme  1.3.4. Serie de potencias  1.4. Discriminación  1.4.1. Teorema del valor medio  1.4.2. Serie de Taylor  1.4.3. Funciones de varias variables  1.4.4. Derivada parcial  1.5. Integración  1.5.1. Integración de Riemann y Lebesgue  1.5.2. Integrales impropias  1.5.3. Teoría de la medida: una herramienta fundamental en la integración  1.5.4. Teorema de Fubini  1.6. Análisis funcional  1.6.1. Comprendiendo los espacios de Banach  1.6.2. Espacios de Hilbert  1.6.3. Operadores en espacios  1.6.4. Teoría espectral
  2. Álgebra abstracta  2.1. Entendiendo los grupos en el álgebra abstracta  2.1.1. Definiciones y ejemplos de grupos en álgebra abstracta  2.1.2. Homomorfismos de grupos  2.1.3. Introducción a los subgrupos normales  2.1.4. Teorema de Sylow  2.2. Anillos y campos  2.2.1. Ideales y anillos cociente  2.2.2. Extensiones de campos  2.2.3. Teoría de Galois  2.2.4. Anillos de polinomios  2.3. Introducción a los módulos en álgebra abstracta  2.3.1. Homomorfismo de módulos  2.3.2. Módulos libres  2.3.3. Introducción a los productos tensoriales  2.3.4. Secuencia exacta en módulos  2.4. Álgebra lineal  2.4.1. Espacio vectorial  2.4.2. Autovalores y autovectores  2.4.3. Espacio de producto interior  2.4.4. Diagonalización
  3. Topología  3.1. Topología general  3.1.1. Conjuntos abiertos y cerrados  3.1.2. Compacidad y conexión  3.1.3. Mapas continuos  3.1.4. Axioma de separación  3.2. Topología algebraica  3.2.1. Comprensión de los grupos fundamentales en la topología algebraica  3.2.2. Homotopía y homología  3.2.3. Complejo simplicial  3.2.4. Secuencias exactas en homología  3.3. Topología diferencial  3.3.1. Comprendiendo las variedades en topología diferencial  3.3.2. Funcionamiento suave  3.3.3. Espacio tangente y cotangente  3.3.4. Fibrados vectoriales
  4. Ecuaciones diferenciales  4.1. Ecuación diferencial ordinaria  4.1.1. Ecuaciones de primer orden  4.1.2. Ecuaciones lineales de segundo orden  4.1.3. Sistemas de ecuaciones diferenciales  4.1.4. Análisis de estabilidad en ecuaciones diferenciales ordinarias  4.2. Ecuaciones en derivadas parciales  4.2.1. Clasificación de EDP  4.2.2. Entendiendo las series de Fourier en ecuaciones diferenciales parciales  4.2.3. Introducción a las funciones de Green  4.2.4. Método de caracterización  4.3. Sistemas dinámicos en ecuaciones diferenciales  4.3.1. Teoría de la sostenibilidad  4.3.2. Ciclos límite en sistemas dinámicos  4.3.3. Teoría del caos  4.3.4. Teoría de bifurcación
  5. Probabilidad y estadística  5.1. Teoría de la probabilidad  5.1.1. Variables aleatorias  5.1.2. Distribuciones de probabilidad  5.1.3. Ley de los grandes números  5.1.4. Teorema del límite central  5.2. Inferencia estadística  5.2.1. Pruebas de hipótesis  5.2.2. Intervalo de confianza  5.2.3. Métodos bayesianos  5.2.4. Estimación de máxima verosimilitud  5.3. Procesos estocásticos  5.3.1. Cadenas de Markov  5.3.2. Movimiento browniano  5.3.3. Comprendiendo los procesos de Poisson  5.3.4. Martingalas: Un estudio integral en probabilidad y estadística
  6. Análisis numérico  6.1. Soluciones numéricas de ecuaciones  6.1.1. Descubrimiento original  6.1.2. Métodos iterativos  6.1.3. Análisis de convergencia  6.1.4. Cotas de error en soluciones numéricas de ecuaciones  6.2. Álgebra lineal numérica  6.2.1. Factorización de matrices  6.2.2. Cálculo de valores propios  6.2.3. Matrices dispersas  6.2.4. Técnicas de preacondicionamiento  6.3. Integración y diferenciación numérica  6.3.1. Métodos de cuadratura  6.3.2. Introducción a las diferencias finitas  6.3.3. Análisis de errores en la integración y diferenciación numérica  6.3.4. Métodos adaptativos en integración y diferenciación numérica
  7. Análisis complejo  7.1. Números complejos  7.1.1. Forma polar  7.1.2. Conjugados complejos  7.1.3. Forma exponencial de los números complejos  7.1.4. Raíces de la unidad  7.2. Funciones analíticas  7.2.1. Ecuaciones de Cauchy–Riemann  7.2.2. Series de potencias  7.2.3. Mapeo conforme  7.2.4. Funciones armónicas  7.3. Integración en el plano complejo  7.3.1. Teorema de Cauchy  7.3.2. Teorema del residuo  7.3.3. Integración de contornos  7.3.4. Transformaciones integrales
  8. Lógica matemática y fundamentos  8.1. Lógica proposicional  8.1.1. Tablas de verdad  8.1.2. Equivalencia lógica en la lógica proposicional  8.1.3. Técnicas de demostración en lógica proposicional  8.1.4. Solución en lógica proposicional  8.2. Lógica de predicados  8.2.1. Cuantificadores en lógica de predicados  8.2.2. Sistemas formales en lógica de predicados  8.2.3. Integridad y solidez  8.2.4. Teoría de modelos  8.3. Teoría de conjuntos  8.3.1. Cardinalidad y ordinalidad  8.3.2. Sistemas axiomáticos  8.3.3. Comprender la teoría de conjuntos de Zermelo-Fraenkel  8.3.4. Fuerzas en la teoría de conjuntos
  9. Personalización  9.1. Programación lineal  9.1.1. Método simplex  9.1.2. Dualidad en la programación lineal  9.1.3. Análisis de sensibilidad en programación lineal  9.1.4. Métodos de punto interior  9.2. Programación no lineal  9.2.1. Descenso de gradiente  9.2.2. Multiplicadores de Lagrange  9.2.3. Optimización convexa  9.2.4. Programación cuadrática  9.3. Optimización Combinatoria  9.3.1. Algoritmos de grafos  9.3.2. Programación entera  9.3.3. Flujo de red  9.3.4. Algoritmos de aproximación
  10. Matemáticas discretas  10.1. Teoría de grafos  10.1.1. Representación de grafos  10.1.2. Llanura y color  10.1.3. Algoritmo de camino más corto  10.1.4. Flujo de red  10.2. Compañerismo  10.2.1. Permutación y combinación  10.2.2. Función generadora  10.2.3. Relación de recurrencia  10.2.4. Comprendiendo el Principio de Inclusión-Exclusión  10.3. Criptografía  10.3.1. Aplicaciones de la teoría de números en criptografía  10.3.2. Criptografía Simétrica y Asimétrica  10.3.3. RSA y criptografía de curvas elípticas  10.3.4. Criptografía post-cuántica

Posgrado → Matemáticas discretas → Teoría de grafos ↓


Algoritmo de camino más corto


En el campo de la teoría de grafos, el problema de encontrar el camino más corto entre nodos en un grafo es un concepto fundamental, con aplicaciones que van desde el enrutamiento de redes hasta la planificación urbana. Para resolver este problema, se han desarrollado varios algoritmos de camino más corto, cada uno con características únicas y casos de uso óptimos. En este documento, exploraremos las ideas clave detrás de estos algoritmos, su funcionamiento y ejemplos prácticos.

Entendiendo el grafo

Antes de adentrarnos en los algoritmos de camino más corto, es importante entender los grafos. Un grafo consiste en vértices (o nodos) y aristas, que pueden ser dirigidas o no dirigidas, ponderadas o no ponderadas. En el contexto de los algoritmos de camino más corto, generalmente nos enfocamos en grafos ponderados, donde cada arista tiene un valor numérico que representa el costo o la distancia de viajar entre los vértices que conecta.

Problema de camino más corto

El problema del camino más corto se trata de encontrar un camino entre dos vértices de manera que la suma de los pesos de sus aristas constituyentes sea mínima. Dependiendo de la naturaleza del grafo y de los requisitos específicos, se utilizan diferentes métodos para encontrar los caminos más cortos.

Algoritmo de Dijkstra

El algoritmo de Dijkstra es uno de los algoritmos más populares para resolver el problema del camino más corto para grafos con pesos de arista no negativos. Es un algoritmo codicioso que trabaja encontrando iterativamente el camino más corto desde el nodo fuente a otros vértices en el grafo.

Funcionamiento del algoritmo de Dijkstra

1. Inicializar la distancia del nodo de origen a 0 y las distancias de todos los otros nodos a infinito.
2. Establecer el nodo de origen como el nodo actual.
3. Para el nodo actual, considerar todos sus vecinos no utilizados y calcular sus distancias temporales desde el nodo de origen.
4. Actualizar la distancia a cada vecino si la nueva distancia calculada es menor que el valor especificado actualmente.
5. Cuando todos los vecinos hayan sido procesados, marcar el nodo actual como visitado.
6. Si el nodo de destino ha sido visitado o la distancia temporal más corta entre nodos es infinita, detener el proceso.
7. De lo contrario, establecer el nodo no utilizado con la distancia temporal más pequeña como el siguiente 'nodo actual' y continuar desde el paso 3.

Ejemplo del algoritmo de Dijkstra

Considera un grafo simple que muestra ciudades conectadas por carreteras, con aristas ponderadas según la distancia a la carretera.

Ilustración del grafo:
    A --4--> B
    A --1--> C
    B --2--> D
    C --2--> B
    C --5--> D

Utilicemos el algoritmo de Dijkstra para encontrar el camino más corto desde la ciudad A a la ciudad D.

A B C D 4 1 2 5 2

Las distancias iniciales son las siguientes:

- A:0
- B : ∞
- C : ∞
- D : ∞

Aplicando el algoritmo de Dijkstra:

  1. Comenzar desde A (sección A, distancia = 0).
  2. B está a 4 de distancia, y C a 1. Actualizar las posibles distancias: B = 4, C = 1.
  3. C está más cerca (distancia = 1). Ahora tomar C como el vértice actual.
  4. Desde C, actualizar la distancia de B a 1 + 2 = 3 (ya que es menor que su inicial 4) y la distancia de D a 1 + 5 = 6.
  5. Ahora, la distancia provisional de B es 3 y la de D es 6. Hacer B el vértice actual ya que es menor.
  6. Actualizar la distancia de B a D como 3 + 2 = 5, que es menor que la distancia estimada anterior de 6.
  7. Ahora, el camino más corto de A a D es de 5 segundos de largo. El algoritmo termina.

Por lo tanto, el camino más corto es A → C → B → D cuya distancia total es 5.

Algoritmo de Bellman–Ford

A diferencia del algoritmo de Dijkstra, el algoritmo de Bellman–Ford puede encontrar caminos más cortos en grafos con aristas de peso negativo y también es capaz de detectar ciclos de peso negativo en grafos. Es menos eficiente en términos de complejidad de tiempo, pero es más versátil para grafos complejos.

Funcionamiento del algoritmo de Bellman-Ford

1. Inicializar la distancia del nodo de origen a 0 y las distancias de todos los otros nodos a infinito.
2. Para cada arista, relajarla: si la distancia actual al nodo de destino a través de esta arista es mayor que la suma de la distancia al nodo fuente y el peso de esta arista, entonces actualizar la distancia al nodo de destino.
3. Repetir el paso 2 un total de |V|-1 veces, donde |V| es el número de vértices.
4. Comprobar ciclos de peso negativo: Para cada arista, si puedes encontrar un camino más corto, entonces existe un ciclo de peso negativo. De lo contrario, se han encontrado los caminos más cortos.

Ejemplo del algoritmo de Bellman-Ford

Considera un grafo con pesas de arista negativas:

Ilustración del grafo:
    A --4--> B
    A ---2--> C
    B --3--> C
    B --5--> D
    C --1--> B
    C --6--> D

Aplicaremos el algoritmo de Bellman-Ford para encontrar el camino más corto desde el nodo A al nodo B:

A B C D 4 -2 5 6 3 1

Las distancias iniciales son las siguientes:

- A:0
- B : ∞
- C : ∞
- D : ∞

Aplicando el algoritmo de Bellman-Ford:

  1. |V|-1 = Después de iterar 3 veces:
    • Para la arista AB: Dist(B) = min(∞, 0 + 4) = 4
    • Para la arista AC: Dist(C) = min(∞, 0 - 2) = -2
    • Para la arista BC: Dist(C) = min(-2, 4 + 3) = -2 (no es necesario actualizar)
    • Para la arista BD: Dist(D) = min(∞, 4 + 5) = 9
    • Para la arista CB: Dist(B) = min(4, -2 + 1) = -1
    • Para la arista CD: Dist(D) = min(9, -2 + 6) = 4
  2. Se crean nuevas distancias:
    3.     - A:0
    - B :-1
    - C: -2
    - D:4
  3. Realizando un ciclo adicional para detectar posibles ciclos de peso negativo no muestra ninguna reducción adicional, por lo que los caminos encontradas son óptimos.

Algoritmo A*

A* es un algoritmo de búsqueda que encuentra el camino más corto entre dos nodos. Es particularmente popular en ciencias de la computación para la búsqueda de caminos y el recorrido de grafos. Lo que hace diferente a A* es su uso de heurísticas para considerar el costo real desde el nodo de inicio así como el costo estimado para alcanzar el objetivo. A* incorpora características del algoritmo de Dijkstra y la búsqueda codiciosa de mejor primero.

Conceptos clave en A*

El algoritmo A* utiliza un grafo ponderado con una función heurística para estimar el costo de alcanzar el objetivo desde cualquier nodo x, denotado como h(x).

El costo total estimado para el nodo n está dado por:

f(n) = g(n) + h(n)
- g(n) es el costo del camino desde el nodo de inicio a n. - h(n) es una función heurística que estima el costo desde n hasta el objetivo.

Ejemplo del algoritmo A*

Considera una cuadrícula en la que los nodos representan un laberinto donde los costos de movimiento varían.

La distancia estimada de los nodos desde el objetivo es h(n), y el costo de los movimientos horizontales/verticales es 1, mientras que el costo de los movimientos diagonales es 1.4.

INICIO ○○○○ OBJETIVO

Ejecutar A* para alcanzar el objetivo desde el inicio utilizando el costo de camino mínimo.

1. Conjunto abierto = {inicio}
2. conjunto_cerrado = {}

3. hasta que el conjunto_abierto esté vacío
    a. actual = nodo con menor f(nodo) en conjunto_abierto
    b. Si el objetivo actual es
        devolver reconstruir_camino(actual)
    
    c. Eliminar actual de conjunto_abierto
    d. Añadir actual a conjunto_cerrado
    
    E. Para cada vecino del flujo
        i. Si el vecino está en el conjunto cerrado
            continuar al siguiente vecino
        
        ii. temp_g = g(actual) + d(actual, vecino)
        
        iii. Si el vecino no está en el conjunto abierto
            Añadir vecino a conjunto_abierto
        iv. sino si el tentativo_g >= g(vecino)
            continuar
        
        v. vino_de[vecino] = actual
        vi. g(vecino) = temp_g
        vii. f(vecino) = g(vecino) + h(vecino)

Al equilibrar eficientemente el costo del camino y las heurísticas, A* encuentra el camino más corto de manera eficiente.

Observaciones finales

Los algoritmos de camino más corto son herramientas indispensables en ciencias de la computación y optimización. Algoritmos como Dijkstra, Bellman-Ford y A* sirven en una variedad de clases de problemas que varían desde la navegación simple en redes hasta la planificación de rutas sofisticada. Comprender estos algoritmos implica entender sus mecanismos, fortalezas, limitaciones y dominios de aplicación.

Al aplicar estos algoritmos, se pueden gestionar eficientemente redes complejas, optimizar la logística y resolver problemas del mundo real, destacando la profunda utilidad de la teoría de grafos en el ámbito más amplio de las matemáticas discretas.

Cada algoritmo proporciona información única sobre las técnicas de recorrido de grafos, asegurando que uno esté bien equipado para enfrentar desafíos diversos en los campos computacionales. El dominio de estos algoritmos fortalece el conocimiento básico, promoviendo la exploración avanzada e innovaciones en estrategias de optimización de redes.


Posgrado → 10.1.3


U
username
0%
completado en Posgrado

← Anterior (10.1.2)
Llanura y color
Siguiente (10.1.4) →
Flujo de red

Comentarios 



Algoritmo de camino más corto

https://www.buddymath.com/g/10.1.3?bmal=es