How does Dijkstra's algorithm actually compute the shortest route?

Dijkstra's algorithm keeps a running best-known distance to every stop, starting at 0 for the source and infinity for everywhere else. At each step it picks the unvisited stop with the smallest known distance, marks it settled, and relaxes every edge leaving it.

What is an exponentially-weighted moving average ETA model, and why does it beat a static timetable?

An EWMA keeps one running estimate per edge and updates it every time a bus actually traverses that edge: new_estimate = alpha * observed_time + (1 - alpha) * old_estimate, so recent observations count more than old ones.

Inicio▸IA y aprendizaje automático▸Predictor de Rutas de Tránsito y ETA

🚌 Predictor de Rutas de Tránsito y ETA

Interactive transit simulator: buses move across a real route network as Dijkstra's algorithm computes shortest paths and a live model predicts arrival times against actual — watch prediction error shrink as buses approach.

IA y aprendizaje automático3DAdvanced60 FPS

Acerca del Predictor de Rutas de Tránsito y ETA

Cada vez que una aplicación de transporte te dice que un autobús está a "4 minutos", dos piezas muy distintas de ciencias de la computación están trabajando juntas entre bastidores. La primera es la búsqueda de ruta más corta: dada una red de paradas y tiempos de viaje, encontrar la ruta más rápida de A a B. La segunda es la predicción de llegada en vivo: dado cómo se ha comportado realmente el tráfico recientemente, estimar cuánto tardará en realidad el siguiente tramo de un viaje — porque un horario impreso es solo una estimación inicial. Esta simulación implementa ambas cosas, de verdad, sobre una red de 16 paradas.

Haz clic en dos paradas cualesquiera para ejecutar una búsqueda genuina de ruta más corta con el algoritmo de Dijkstra entre ellas: observa cómo la frontera de paradas "resueltas" se expande hacia afuera y la ruta final se resalta una vez encontrada. Mientras tanto, hasta cuatro autobuses circulan continuamente por rutas fijas. Cada arista de la red tiene un factor de tráfico que fluctúa aleatoriamente, y un modelo de media móvil ponderada exponencialmente aprende en vivo el tiempo de viaje actual de cada arista a partir de cada autobús que la cruza — de modo que los ETA predichos se adaptan a las condiciones en lugar de seguir un horario fijo. Un gráfico en vivo registra cuánto se alejan las predicciones de la realidad a medida que cambia la volatilidad del tráfico.

Preguntas Frecuentes

¿Cómo calcula realmente el algoritmo de Dijkstra la ruta más corta?

El algoritmo de Dijkstra mantiene una mejor distancia conocida hasta el momento para cada parada, comenzando en 0 para el origen e infinito para todo lo demás. En cada paso elige la parada no visitada con la menor distancia conocida, la marca como resuelta, y relaja cada arista que sale de ella: si pasar por la parada resuelta da una ruta más corta a un vecino que la mejor actual del vecino, se actualizan esa mejor distancia y su predecesor. Como las paradas siempre se resuelven en orden de distancia creciente, una vez que una parada está resuelta su distancia nunca puede mejorar de nuevo, y el algoritmo se detiene en cuanto se resuelve el destino. Recorrer los punteros de predecesor hacia atrás desde el destino reconstruye la ruta más corta real.

¿Qué es un modelo de ETA de media móvil ponderada exponencialmente, y por qué supera a un horario estático?

Un horario estático asume que cada viaje a lo largo de un tramo toma la misma duración programada sin importar las condiciones. Una media móvil ponderada exponencialmente (EWMA), en cambio, mantiene una estimación en curso por cada arista y la actualiza cada vez que un autobús realmente la recorre: nueva_estimación = α · tiempo_observado + (1 − α) · estimación_anterior. Como α está entre 0 y 1, las observaciones recientes cuentan más que las antiguas, de modo que la estimación sigue las condiciones actuales sin dejar de suavizar el ruido puntual de un viaje inusualmente rápido o lento. Esta simulación usa α = 0.3.

¿Por qué el error de predicción se dispara cuando se aumenta la volatilidad del tráfico?

El modelo EWMA solo puede reaccionar después de observar un viaje completado, por lo que es fundamentalmente un indicador rezagado. Cuando el control deslizante de volatilidad aumenta lo abruptamente que oscilan los factores de tráfico por arista, se amplía la brecha entre "lo último que aprendió el modelo" y "lo que realmente está ocurriendo ahora", por lo que crece el error absoluto medio entre los horarios de llegada predichos y los reales.

¿Por qué cambia la ruta más corta aunque el mapa en sí nunca se mueve?

Esta simulación ejecuta Dijkstra usando el tiempo de viaje predicho en vivo por EWMA de cada arista en lugar de su distancia física fija, por lo que una consulta para las mismas dos paradas puede devolver una ruta distinta una vez que las condiciones del tráfico han cambiado los pesos aprendidos lo suficiente como para que una ruta antes más lenta se vuelva la más rápida.

⚙ Bajo el capó

Los autobuses se desplazan por una red de rutas mientras el algoritmo de Dijkstra calcula las rutas más cortas y un modelo en vivo predice los horarios de llegada.

Three.jsWebGLIAAprendizaje Automático

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install