Math
La ruta más barata
Terreno donde un paso cuesta el precio de la celda en la que entras, y la ola de vértices cerrados se extiende por PRECIO, no por distancia. Un control pone una arista negativa en el mapa y tiene tres tramos medidos.
Qué ocurre
Aquí un paso cuesta el precio de la celda en la que entras, así que la ola de vértices cerrados no se extiende en círculos: corre lejos por una hondonada barata y se detiene ante una loma cara. Esa imagen es toda la diferencia entre una búsqueda en anchura y esta. Mientras los pesos no sean negativos la respuesta es demostrablemente mínima, y aquí se comprueba contra Bellman-Ford relajado hasta el punto fijo - nunca contra una segunda pasada del mismo algoritmo - y en rejillas pequeñas contra la enumeración completa de caminos simples. En terreno llano el coste tiene forma cerrada, w(i + j), porque toda ruta monótona cuesta lo mismo. Los contadores también son identidades: cada vértice se cierra exactamente una vez y cada arista se relaja exactamente una vez, 4m(m−1) de ellas. Después el control deja caer una sola arista dirigida negativa, y tiene tres tramos, todos medidos y no descritos. Hasta −15 no se rompe nada: una arista negativa por sí sola no es un problema. De −16 a −50 Dijkstra responde 93 donde la verdad es 92, luego 78, luego 58 - siempre DE MÁS, porque un vértice cerrado no se reabre - y junto a la ruta amarilla aparece la verdadera, para que el error se vea en lugar de afirmarse. En −51 aparece un ciclo negativo: no hay ruta mínima en absoluto, Bellman-Ford lo dice, y Dijkstra imprime los mismos 93 sin inmutarse.
Ecuaciones del módulo
Ecuaciones terreno en una cuadrícula m x m, cada celda con precio 1..9, un paso cuesta el precio de la celda en la que entras; inicio arriba a la izquierda, meta abajo a la derecha con pesos no negativos Dijkstra acierta - comprobado frente a Bellman-Ford relajado hasta un punto fijo, y en 3x3 y 4x4 frente a una enumeración COMPLETA de caminos simples el terreno plano tiene forma cerrada: coste hasta (i, j) = w(i + j), así que la meta cuesta w·2(m−1) - 120 con w = 5, m = 13 vértices fijados = m² (cada uno cerrado exactamente una vez); relajaciones = aristas = 4m(m−1) = 624 con m = 13; inserciones en el montículo 169 en el terreno por defecto 13x13 por defecto, descuento desactivado: la ruta más barata hasta la meta 93, los mismos 93 de Bellman-Ford, 25 celdas en la ruta, 0 celdas donde los dos discrepan una arista de descuento dirigida de (0,7) a (5,0), y el deslizador tiene TRES regímenes, todos medidos: hasta −15: ningún error - una arista negativa no es por sí sola un problema −16 a −50: Dijkstra devuelve 93 mientras que la verdad es 92, 78, 58 - siempre DEMASIADO GRANDE, y las respuestas discrepan en 65, 122, 159 de las 169 celdas −51 y menos: un ciclo negativo - no hay camino más corto, Bellman-Ford lo dice, y Dijkstra aun así imprime 93 los extremos de la arista de descuento se eligieron enumerando todos los pares: la ventana necesita d(lejos) − d(cerca) < k < cost(de cerca a lejos), y está vacía cuando la ruta barata a la celda lejana pasa por la cercana
