Algoritmo Bellman Ford: Guía de entrevistas de codificación

TL;DR: El algoritmo de Bellman Ford encuentra los caminos más cortos de una sola fuente en un gráfico dirigido ponderado, incluso cuando algunos bordes tienen pesos negativos. Inicialice la distancia de la fuente a cero, todas las demás al infinito, relaje cada borde hasta V menos 1 veces, luego haga una pasada adicional: cualquier mejora adicional demuestra que existe un ciclo de peso negativo alcanzable.

¿Qué es el algoritmo de Bellman Ford?

Bellman Ford es un algoritmo de ruta más corta de estilo de programación dinámica. Después del primer paso completo, los caminos más conocidos utilizan como máximo un borde; después del segundo, como máximo dos aristas. Una ruta simple contiene como máximo V menos 1 aristas, lo que explica tanto el recuento de bucles como el argumento de corrección. A diferencia del algoritmo de Dijkstra, Bellman Ford no supone pesos de borde no negativos.

¿Cómo se explica la relajación de los bordes?

Para una arista de u a v con peso w, la relajación pregunta si la distancia [u] + w es menor que la distancia [v]. Realice la suma solo cuando u esté disponible. Si el candidato es mejor, actualice la distancia [v] y establezca el predecesor [v] en u. La matriz predecesora es opcional para distancias, pero le permite reconstruir la ruta real y explicar el resultado claramente.

¿Cómo se rastrea a Bellman Ford en una entrevista?

Utilice un gráfico pequeño y escriba una fila de distancia por pasada. Comience con la fuente A en 0 y cada dos vértices en el infinito. Escanee la lista completa de bordes en un orden coherente y registre cada actualización. Deténgase temprano cuando un pase completo no realice cambios. Sea explícito que el orden de los bordes puede cambiar las filas intermedias pero no las distancias finales correctas cuando no existe un ciclo negativo alcanzable.

¿Qué pseudocódigo deberías escribir?

Cree matrices de distancia y predecesoras, luego repita un escaneo de borde completo V menos 1 veces. Utilice un indicador modificado para la terminación anticipada. Finalmente, escanee todos los bordes una vez más e informe un ciclo negativo si aún se puede mejorar una distancia alcanzable. En el código de producción, elija un tipo numérico que pueda contener sumas de rutas y proteger el centinela infinito antes de la suma.

¿Cuáles son las complejidades del tiempo y el espacio?

La implementación estándar de lista de bordes de adyacencia se ejecuta en tiempo O(VE) porque puede escanear bordes E en cada una de las pasadas V menos 1, más una pasada de detección. Utiliza espacio auxiliar O(V) para distancias y predecesores. La interrupción anticipada mejora los datos favorables, pero el límite del peor de los casos sigue siendo O(VE).

¿Cuándo debería elegir Bellman Ford en lugar de Dijkstra?

Elija Bellman Ford cuando se permitan pesos de borde negativos o cuando el entrevistador solicite explícitamente una detección de ciclo negativo accesible. Elija Dijkstra con una cola de prioridad para gráficos cuyos pesos de borde no sean negativos porque normalmente es más rápido. Para los caminos más cortos de todos los pares, primero aclare la densidad del gráfico, los pesos negativos y si se requieren caminos o solo distancias.

¿Qué errores deberías evitar?

No te relajes desde un vértice inalcanzable, no confundas un borde negativo con un ciclo negativo, ni afirmes que cada ciclo negativo invalida el resultado: sólo un ciclo alcanzable desde la fuente afecta sus caminos más cortos. También evite ejecutar solo V menos 2 pasadas, saltarse la pasada de detección final o reconstruir una ruta sin mantener los predecesores.

¿Cómo puedes practicar la explicación?

Practique tres versiones: una definición de 30 segundos, una explicación de corrección de dos minutos y una implementación completa. Pruebe un vértice inalcanzable, un borde negativo sin ciclo, un ciclo negativo alcanzable y un gráfico que se estabilice temprano. Esto separa el código memorizado de la comprensión genuina.

Utilice la IA para organizar el material que ya comprende, ensayar explicaciones y revisar su actuación. Siga las reglas del empleador y del proveedor de evaluaciones y nunca invente experiencias, números o resultados.

Continúe con la guía del copiloto de entrevistas de IA, preparación basada en currículum vitae y flujo de trabajo de revisión posterior a la entrevista.

Preguntas frecuentes

Practique con evidencia, no con un guión

YesToTheOffer puede preparar la base y estructurar las respuestas en tiempo real en su currículum, descripción de funciones y notas privadas, y luego conservar una transcripción para su revisión posterior a la entrevista.