1. Elige el algoritmo
2. Carga un grafo de ejemplo o construye el tuyo
3. Edita el grafo
Modo añadir nodo: haz clic en el lienzo para crear un nodo nuevo.
BFS, DFS, Dijkstra y A* — paso a paso con estructura auxiliar viva
BFS, DFS, Dijkstra y A* — comparativa y casos de uso
| Algoritmo | Estructura auxiliar | Aristas con peso | Camino óptimo | Complejidad | Cuándo usar |
|---|---|---|---|---|---|
| BFS | Cola FIFO | No (ignora peso) | Sí, en aristas | O(V + E) | Camino más corto en aristas (sin peso) |
| DFS | Pila LIFO | No (ignora peso) | No | O(V + E) | Detectar ciclos, ordenación topológica, exploración |
| Dijkstra | Cola de prioridad (heap) | Sí (no negativos) | Sí, en peso | O((V+E) log V) | Camino más corto en grafos con peso (mapas, redes) |
| A* | Heap por f = g + h | Sí (no negativos) | Sí, si h es admisible | O((V+E) log V) | Pathfinding con destino conocido (videojuegos, GPS) |
Google Maps, Waze y aplicaciones similares usan variantes de Dijkstra y A* sobre grafos donde nodos son intersecciones y aristas son tramos de carretera con peso = tiempo o distancia.
A* gana a Dijkstra cuando se conoce el destino, gracias a la heurística geográfica.
El pathfinding de personajes no jugables (NPCs) en juegos de estrategia, RPG o shooters se resuelve con A* sobre grids o navmesh, con heurística manhattan o euclídea.
BFS también se usa en juegos por turnos para casillas alcanzables en N pasos.
Protocolos como OSPF (Open Shortest Path First) usan Dijkstra para construir tablas de enrutamiento. Los routers calculan el mejor camino al destino en tiempo real.
BGP es un caso especial: usa políticas, no solo coste mínimo.
«Personas que quizás conozcas» en LinkedIn o Facebook se calcula con BFS limitado a 2-3 niveles de profundidad sobre el grafo de amistad.
BFS mantiene el orden por distancia social: primero amigos, luego amigos-de-amigos.
BFS explora «por niveles»: visita primero todos los vecinos directos, luego los vecinos de los vecinos, y así sucesivamente. Usa una cola FIFO. DFS explora «a fondo»: sigue un camino hasta agotarlo y vuelve hacia atrás (backtracking) cuando no puede avanzar. Usa una pila LIFO (o recursión).
BFS encuentra el camino más corto en número de aristas. DFS no garantiza camino óptimo, pero usa menos memoria en grafos profundos.
Dijkstra asume que una vez que extraes un nodo del heap (con la menor distancia), esa distancia es definitiva: no puede mejorar. Con pesos negativos, una arista posterior podría reducir la distancia, invalidando esa decisión.
Si tu grafo tiene aristas con peso negativo, usa Bellman-Ford (O(V·E)) o Floyd-Warshall (todos los pares).
Una heurística h(n) estima el coste desde n hasta el destino. Debe ser admisible (nunca sobreestimar el coste real) para garantizar la optimalidad. Heurísticas comunes: distancia euclídea (rejillas con movimiento libre), distancia Manhattan (rejillas 4-direcciones), distancia Chebyshev (rejillas 8-direcciones).
Cómo la calcula este simulador. Aquí los pesos los pones tú con un deslizador y no tienen ninguna relación con las distancias del dibujo, así que la distancia en píxeles a secas NO sería admisible: podría estimar 30 donde el camino entero cuesta 10, y entonces A* dejaría de garantizar el óptimo. Por eso h se calibra con el propio grafo — h(n) = k · distancia(n, destino), donde k es el menor cociente peso/longitud de todas sus aristas. Si ninguna arista cuesta menos de k por píxel, ningún camino puede costar menos de k veces la línea recta, y la heurística queda garantizada por debajo del coste real.
Si h = 0, A* degenera a Dijkstra. Si h sobreestima, encuentra camino rápido pero no óptimo.
Cuando hay un destino concreto y se puede calcular una buena heurística. A* dirige la búsqueda hacia el destino, evitando explorar zonas alejadas. En grafos sin geometría (sin coordenadas), no hay heurística natural y Dijkstra suele ser más sencillo.
Si necesitas el camino más corto desde un origen a todos los nodos, usa Dijkstra (no A*).
En un grafo dirigido, cada arista tiene sentido: A→B no implica B→A. Se usa para modelar relaciones asimétricas: calles de una sola dirección, dependencias, «sigue a» en redes sociales. En un grafo no dirigido, las aristas son simétricas: A↔B significa que se puede ir en ambos sentidos.
Internamente, un grafo no dirigido se puede ver como dirigido con dos aristas opuestas por cada conexión.
Un heap binario es un árbol donde cada padre es menor (min-heap) o mayor (max-heap) que sus hijos. Insertar y extraer-mínimo son O(log n). En la mayoría de lenguajes hay implementaciones nativas: heapq en Python, PriorityQueue en Java, o librerías en JavaScript.
Para grafos pequeños, una lista ordenada (O(n) por extracción) basta. Para grafos grandes, el heap marca diferencia.
Dibuja los nodos y aristas. Para BFS prepara una cola; para DFS una pila; para Dijkstra una tabla de distancias (origen=0, resto=∞) y una cola de prioridad; para A* añade columnas g, h, f.
Añade el nodo origen a la cola/pila/heap. Marca su distancia (0 en BFS niveles; 0 en Dijkstra; g=0, f=h en A*).
Saca el siguiente nodo: el primero en BFS, el último en DFS, el de menor distancia en Dijkstra, el de menor f en A*. Márcalo como visitado.
Para cada vecino no visitado, añádelo a la estructura. En Dijkstra/A*, comprueba si llegar por este camino mejora su distancia: si sí, actualiza dist[vecino] y guarda predecesor.
Si la estructura queda vacía sin haber visitado el destino, no existe camino. Si llegas al destino, reconstruye el camino siguiendo los predecesores hacia atrás.
Lista de adyacencia para grafos dispersos (la mayoría). Matriz de adyacencia solo si V es pequeño y necesitas consultas O(1) por par (i,j).
Cola FIFO para BFS, pila o recursión para DFS, heap binario para Dijkstra/A*. Una mala elección multiplica la complejidad.
En Dijkstra, un nodo puede entrar al heap varias veces con diferentes distancias. Solo se considera definitivo al extraerse.
h(n) nunca debe sobreestimar el coste real. Distancia euclídea es admisible si los pesos son distancias geométricas; Manhattan lo es en grids 4-direcciones.
Si la estructura auxiliar queda vacía sin haber alcanzado el destino, no existe camino. Devuelve un valor especial (null, -1, ∞).
No guardes caminos completos en cada nodo (gasto de memoria). Guarda solo «de quién vine» y reconstruye al final siguiendo la cadena hacia atrás.