Digamos que vamos del 1 al 5. La ruta más corta será 1-4-3-5 (total: 60 km).
Podemos usar el algoritmo de Dijkstra para hacer eso.
Ahora el problema es que la ruta más corta no siempre es la más rápida debido a los atascos de tráfico u otros factores.
Por ejemplo:
- Se sabe que 1-2 tiene atascos frecuentes, por lo que debe evitarse.
- De repente, se produce un accidente automovilístico a lo largo de 4-3, por lo que también debe evitarse.
- Etc ...
Entonces, probablemente podamos acelerar en la ruta 1-4-5, debido a que no hay atascos / accidentes, por lo que llegaremos a 5 más rápido.
Bueno, esa es la idea general, y aún no he pensado en más detalles.
¿Hay algún algoritmo para resolver este problema?
Respuestas:
Dado que trajiste congestión en la imagen, ten cuidado de que no te atrape la paradoja de Braess . Si todos eligen el camino óptimo, el tiempo de viaje es peor para todos.
fuente
Sí: Dijkstra
Dijkstra funciona igual de bien para esta situación.
Simplemente usa el tiempo en lugar de la distancia como el peso de cada arco.
fuente
Si. El algoritmo de Dijkstra resolverá este problema.
El problema en su caso es que automáticamente asume que la ruta más corta equivale a la distancia recorrida, cuando en realidad equivale más apropiadamente al COSTO de tomar una ruta.
Si una ruta tiene un obstáculo, su COSTE debería ser mayor, y el algoritmo aún se aplica.
fuente
Debería poder reemplazar su distancia con el tiempo entre nodos y resolverla de la misma manera.
fuente
Dijkstra
Como se dijo antes, no solo se usa para la distancia más corta. Creo que esta animación da una buena comprensión del "poder" (a falta de una palabra mejor) de Dijkstra:
fuente