Dijkstra algoritmo de ruta más corta con un costo borde

Question

I tiene una dirigida, grafo ponderado positivo. Cada arista tiene un costo de uso. Sólo tengo un dinero, quiero calcular los caminos más cortos con Dijkstra algoritmo, pero suma de los costos de los bordes en la ruta debe ser menor o igual a a.

Quiero hacer esto con más mínima alteración Dijstra (si puedo hacerlo con una pequeña modificación de Dijkstra). Debo hacer esto en O(n*log(n)) si puedo, pero yo creo que pueda.

Cualquiera puede ayudarme con esto?

Answer 1

https://www.spoj.pl/problems/ROADS/

El problema se da en CEOI '98 y su solución oficial se puede encontrar aquí .

Answer 2

En realidad, no resulta necesario modificar el algoritmo de Dijkstra para hacer esto como la respuesta es equivalente a encontrar el camino más corto y luego aceptarla si es menor o igual a a.

Por supuesto, usted podría circuito siempre se corta el bucle interno si se visita un camino con un costo de más de A.

EDIT: Con la aclaración de que desea reducir al mínimo costo y la distancia, no se puede hacer eso sin aclarar la solución que desea. ¿Quieres que la ruta más barata? ¿Desea que el camino más corto? ¿Quieres un poco en función del costo y la distancia? Todas estas determinar qué función de ponderación que debe utilizar para un borde concreto.