Caminos más cortos con reembolsos
La misión
Problema
Una región tiene n pueblos numerados de 0 a n - 1 y carreteras de un solo sentido dadas como [u, v, cost]. Algunas carreteras pagan un reembolso, así que su costo es negativo, pero ningún ciclo de carreteras tiene un total negativo. Devuelve el costo más barato desde el pueblo src hasta cada pueblo, usando None para los pueblos a los que no se puede llegar.
Ejemplos
Input: n = 4, roads = [[0, 1, 4], [0, 2, 5], [2, 1, -3], [1, 3, 2]], src = 0
Output: [0, 2, 5, 4]
Por qué: ir de 0 a 2 y luego a 1 cuesta 5 - 3 = 2, menos que la carretera directa a 1, que cuesta 4
Input: n = 3, roads = [[0, 1, -2]], src = 0
Output: [0, -2, None]
Por qué: ninguna carretera llega al pueblo 2
Input: n = 1, roads = [], src = 0
Output: [0]
Por qué: caso límite: llegar al pueblo de inicio no cuesta nada
Pistas
0 / 3
En el primer ejemplo, el pueblo 1 parece fijado con costo 4 antes de que aparezca la carretera con reembolso que pasa por el pueblo 2. ¿Por qué eso rompe el enfoque habitual de fijar primero lo más barato?
Relajar una carretera significa bajar el costo de su pueblo final si pasar por su pueblo inicial es más barato. Un camino más barato tiene como máximo n - 1 carreteras, y cada pasada completa sobre las carreteras fija al menos una carretera más de cada camino más barato.
Pon todos los costos en infinito excepto el de src. Repite n - 1 veces: relaja cada carretera. Detente antes si una pasada completa no cambia nada. Convierte en None los costos que sigan en infinito.
- Tiempo objetivo
- O(n · m)
- Espacio objetivo
- O(n)
Restricciones
- towns are numbered 0 to n - 1
- road costs may be negative
- no loop of roads has a negative total
Solución
Bellman-Ford no confía en ningún costo hasta que se hayan hecho suficientes pasadas. Después de la pasada k, cada pueblo cuyo camino más barato usa como máximo k carreteras tiene su costo final, porque la última carretera de ese camino se relajó cuando su penúltimo pueblo ya tenía el costo correcto. Si ningún ciclo tiene un total negativo, un camino más barato nunca repite un pueblo, así que n - 1 pasadas bastan, y una pasada sin cambios significa que todos los costos ya son finales. Buscar primero lo más barato falla aquí porque una carretera con reembolso encontrada más tarde puede abaratar un pueblo que ya se había fijado. El tiempo es O(n · m) para m carreteras, y el espacio es O(n).
def cheapest_from(n, roads, src):
INF = float("inf")
cost = [INF] * n
cost[src] = 0
for _ in range(n - 1): # a cheapest path uses at most n - 1 roads
changed = False
for u, v, c in roads:
if cost[u] != INF and cost[u] + c < cost[v]:
cost[v] = cost[u] + c # relax the road
changed = True
if not changed: # nothing moved: every cost is final
break
return [x if x != INF else None for x in cost]
print(cheapest_from(4, [[0, 1, 4], [0, 2, 5], [2, 1, -3], [1, 3, 2]], 0)) # -> [0, 2, 5, 4]
print(cheapest_from(3, [[0, 1, -2]], 0)) # -> [0, -2, None]
print(cheapest_from(1, [], 0)) # -> [0]¿Lo que te frena es la idea y no el código? Bellman-Ford lo explica.