Jonathan, aí precisaria estudar melhor o problema, mas seguem algumas ideias:
Modificação da função de custo: Atribua um custo infinito às arestas que representam trilhos com bondes quebrados ou em manutenção, ou utilize uma função de custo que considere o tempo de espera estimado para reparo ou o impacto na operação da linha de bonde, por exemplo, o custo é uma função do tempo de espera estimado.
Remoção temporária de arestas: Remova temporariamente do grafo as arestas que representam trilhos com restrições. O algoritmo vai ignorar automaticamente esses caminhos indisponíveis, buscando alternativas viáveis. As arestas podem ser reinseridas no grafo quando as restrições forem removidas.
Implementação de regras de priorização: Utilize heurísticas que considerem a probabilidade de restrições em diferentes trilhos, direcionando a busca para caminhos mais confiáveis, por exemplo, o custo tem um fator que é calculado em função da probabilidade de manutenção na linha.