Menores caminhos com reembolsos
A missão
Problema
Uma região tem n cidades numeradas de 0 a n - 1 e estradas de mão única dadas como [u, v, cost]. Algumas estradas pagam um reembolso, então o custo delas é negativo, mas nenhum ciclo de estradas tem total negativo. Retorne o menor custo da cidade src até cada cidade, usando None para as cidades que não podem ser alcançadas.
Exemplos
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 e depois a 1 custa 5 - 3 = 2, menos que a estrada direta até 1, que custa 4
Input: n = 3, roads = [[0, 1, -2]], src = 0
Output: [0, -2, None]
Por quê: nenhuma estrada leva à cidade 2
Input: n = 1, roads = [], src = 0
Output: [0]
Por quê: edge case: chegar à cidade inicial não custa nada
Dicas
0 / 3
No primeiro exemplo, a cidade 1 parece finalizada com custo 4 antes que a estrada com reembolso que passa pela cidade 2 seja vista. Por que isso quebra a abordagem habitual de pegar o mais barato primeiro?
Relaxar uma estrada significa baixar o custo da cidade onde ela termina se passar pela cidade onde ela começa sair mais barato. Um caminho mais barato tem no máximo n - 1 estradas, e cada passada completa pelas estradas acerta pelo menos mais uma estrada de todo caminho mais barato.
Defina todo custo como infinito, exceto o de src. Repita n - 1 vezes: relaxe cada estrada. Pare antes se uma passada inteira não mudar nada. Transforme em None os custos que continuarem infinitos.
- Tempo-alvo
- O(n · m)
- Espaço-alvo
- O(n)
Restrições
- towns are numbered 0 to n - 1
- road costs may be negative
- no loop of roads has a negative total
Solução
O Bellman-Ford não confia em nenhum custo até que passadas suficientes tenham rodado. Depois da passada k, toda cidade cujo caminho mais barato usa no máximo k estradas tem seu custo final, porque a última estrada desse caminho foi relaxada depois que a penúltima cidade já estava correta. Um caminho mais barato nunca repete cidade quando nenhum ciclo tem total negativo, então n - 1 passadas bastam, e uma passada sem mudança significa que todo custo já é final. A busca que pega o mais barato primeiro falha aqui porque uma estrada com reembolso encontrada depois pode baratear uma cidade que ela já tinha finalizado. O tempo é O(n · m) para m estradas, e o espaço é 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]Travou na ideia, e não no código? Bellman-Ford explica isso.