Explora grafos famosos, ejecuta el algoritmo de Dijkstra paso a paso y descubre propiedades como caminos de Euler y Hamilton
Encuentra el camino más corto entre dos nodos. Haz clic en los botones para seleccionar origen y destino, luego ejecuta el algoritmo.
Google Maps usa Dijkstra y A* sobre un grafo de millones de intersecciones para calcular rutas óptimas en milisegundos.
El protocolo BGP que conecta todos los routers de internet es un algoritmo de camino mínimo en un grafo global.
Facebook y LinkedIn modelan conexiones como grafos. Los "grados de separación" son distancias BFS en ese grafo.
Las reacciones químicas del metabolismo celular forman un grafo. Los algoritmos de grafos identifican rutas metabólicas clave.
Cada estación es un nodo, cada conexión una arista. El planificador de viajes en metro es Dijkstra con pesos de tiempo.
Las moléculas se representan como grafos donde los átomos son nodos y los enlaces covalentes son aristas.
Desde los Puentes de Königsberg hasta los algoritmos modernos
Un grafo G = (V, E) es una estructura matemática compuesta por un conjunto de vértices (o nodos) V y un conjunto de aristas (o arcos) E que los conectan. Es la estructura perfecta para modelar relaciones entre entidades.
Las aristas no tienen dirección: si existe una arista entre A y B, puedes ir de A a B y de B a A. Ejemplo: red de amistades en Facebook.
Las aristas tienen dirección (flechas). Ejemplo: Twitter (seguir no es recíproco), páginas web (hiperenlaces).
Cada arista tiene un peso numérico (distancia, coste, tiempo). Esencial para algoritmos de camino mínimo como Dijkstra.
Nodos divididos en dos grupos donde las aristas solo conectan grupos distintos. Ejemplo: usuarios y productos (plataformas de recomendación).
En 1736, Leonhard Euler resolvió el problema de si era posible cruzar los 7 puentes de Königsberg (actual Kaliningrado) pasando exactamente una vez por cada uno. Su solución negativa fundó la teoría de grafos.
Euler modeló las masas de tierra como nodos y los puentes como aristas. Demostró que un camino de Euler (recorrer todas las aristas exactamente una vez) solo existe si hay exactamente 0 o 2 nodos con grado impar. Como los 4 nodos de Königsberg tienen grado impar, es imposible.
Visita todas las aristas exactamente una vez. Los nodos pueden repetirse.
Complejidad: O(E) — resoluble en tiempo polinomial
Condición: 0 o 2 nodos con grado impar
Ejemplo real: Cartero que recorre todas las calles de un barrio
Visita todos los nodos exactamente una vez. Las aristas pueden no usarse.
Complejidad: NP-completo — no hay algoritmo eficiente conocido
Condición: No existe condición simple equivalente a la de Euler
Ejemplo real: Problema del viajante de comercio (TSP)
Esta asimetría es fascinante: dos problemas que parecen similares tienen complejidades computacionales radicalmente distintas. Euler se puede resolver en tiempo lineal; Hamilton es NP-completo (posiblemente imposible de resolver eficientemente para grafos grandes).
Edsger Dijkstra publicó su algoritmo en 1959. Resuelve el problema del camino mínimo desde un nodo fuente a todos los demás nodos en un grafo con pesos no negativos.
Distancia del nodo origen = 0. Distancia de todos los demás = ∞. Crear conjunto de nodos no visitados.
Del conjunto de nodos no visitados, elegir el que tenga distancia mínima conocida.
Para cada vecino del nodo actual: si distancia_actual + peso_arista < distancia_vecino, actualizar distancia_vecino.
El nodo procesado nunca volverá a actualizarse (su distancia mínima ya es definitiva).
Cuando el destino es el nodo seleccionado en el paso 2, el algoritmo termina.
Existe un camino entre cualquier par de nodos. Si eliminamos un nodo y el grafo queda disconexo, ese nodo es un punto de articulación.
Grafo conexo sin ciclos. Siempre tiene exactamente n-1 aristas para n nodos. Ejemplo: estructura de directorios del sistema operativo.
Cada nodo conectado con todos los demás. Tiene n(n-1)/2 aristas. K5 y K3,3 no son planares (no se pueden dibujar sin cruzar aristas).
Se puede dibujar en un plano sin que las aristas se crucen. Fórmula de Euler: V - E + F = 2 (vértices, aristas, caras). Los mapas geográficos son planares.
Nodos en dos grupos; aristas solo entre grupos. Un grafo es bipartito si y solo si no tiene ciclos impares. Usado en matching y recomendaciones.
Grafo dirigido sin ciclos. La base de git commits, dependencias de paquetes npm, pipelines de datos y blockchain.
Los 7 Puentes de Königsberg (1736) son el problema que fundó toda la teoría de grafos. Euler demostró que era imposible cruzarlos todos exactamente una vez — no por ensayo y error, sino con una demostración matemática elegante basada en los grados de los nodos. Hoy esa ciudad se llama Kaliningrado y solo quedan 5 de los 7 puentes originales... pero el legado matemático persiste en cada GPS, red social y motor de búsqueda del planeta.