Significado y funcionamiento
La gráfica representa las posiciones como vértices y las relaciones móviles como aristas. El costo de una ruta se define como la suma de los costos de las aristas recorridas o los costos asignados a cada vértice.
La búsqueda en anchura se expande en función del número de movimientos en los bordes con costos iguales. El algoritmo de Dijkstra selecciona candidatos basado en el costo acumulado mínimo actual.
Relaciones y condiciones de validez
La función de relajación actualiza d(v) a min(d(v), d(u)+w(u,v)). Cuando se encuentra una ruta más económica, tanto la distancia como la información del predecesor se actualizan.
El procedimiento estándar para el algoritmo de Dijkstra se basa en la condición de que no existen pesos negativos. El experimento utiliza únicamente movimientos hacia arriba, hacia abajo, hacia la izquierda y hacia la derecha, con costos positivos, mientras que se omiten movimientos diagonales o restricciones de carreteras reales.
Qué observar en la simulación
BFS minimiza pasos; Dijkstra minimiza el coste total.
Movimientos ortogonales y costes positivos; preajustes reproducibles fijan muros y extremos.
Relaciones y símbolos clave
d(v) = min[d(u) + w(u,v)]
| Símbolo | Significado | Unidad |
|---|---|---|
| d(v) | Estimación actual de la distancia desde el origen hasta v | Coste |
| w(u,v) | Coste de desplazarse de u a v | Coste |
Ejemplo resuelto
Con costes iguales, ¿cómo son las distancias mínimas?
Iguales · BFS minimiza pasos; Dijkstra minimiza el coste total.
Errores frecuentes
- No es cierto que la búsqueda en anchura minimice el costo para todos los grafos con diferentes pesos de arista.