¿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, lanza un error o devuelve null.
bellmanFord(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, a diferencia de Dijkstra.
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 console.log() para depurar. Los resultados aparecen en la Consola de salida, no en el navegador.