¿Quieres un reto mayor?
Resuelve en 20:00
Importante: Para que se registre el resultado tienes que iniciar sesión.
Este ejercicio fue usado en una prueba técnica de empleo.
Algoritmo de Bellman-Ford
Enunciado
Adaptado de Daily Coding Problem.
Dado un grafo dirigido con n nodos (numerados del 0 al n-1), una lista de aristas edges donde cada arista es [u, v, w] (de u a v con peso w), y un nodo origen src, devuelve un array con las distancias mínimas desde src a todos los demás nodos.
Si un nodo no es alcanzable, su distancia es -1. Si el grafo contiene un ciclo negativo alcanzable desde src, devuelve None.
bellman_ford(5, [[0,1,-1],[0,2,4],[1,2,3],[1,3,2],[1,4,2],[3,2,5],[3,1,1],[4,3,-3]], 0)
# [0, -1, 2, -2, 1]
El algoritmo de Bellman-Ford puede manejar pesos negativos y detectar ciclos negativos.
Restriccionesexpand_more
- Dificultad: Master
- Completa todos los test cases para obtener los 150 puntos.
- No modificar la línea
exportal final del archivo. - Se recomienda evitar el uso de inteligencia artificial para que realmente tú practiques los ejercicios.
Puedes usar print() para depurar. Los resultados aparecen en la Consola de salida, no en el navegador.