← Volver a los ejercicios

Distancias

La distancia δ(s, v) es el peso mínimo de un camino de s a v. Con pesos puede ser un entero, ∞ cuando no hay camino, o −∞ cuando algún camino pasa por un ciclo de peso negativo y se puede abaratar sin límite. Cada grafo trae una fuente s y varios vértices; hay que escoger la distancia de cada uno entre las opciones (un entero, ∞ o −∞) y después leer, vértice por vértice, el camino o el ciclo que la justifica.

1. El grafo

Grafo:

La fuente s va en verde. Los números sobre las flechas son los pesos.

2. Escoja δ(s, v) para cada vértice

3. Para llevarse

Si el grafo no tiene ciclos negativos, ¿por qué un camino más corto no necesita repetir vértices?

Suponga un camino más corto de s a v que pasa dos veces por el mismo vértice x. El tramo entre las dos visitas es un ciclo C. Sin ciclos negativos, el peso de C es mayor o igual que cero. Si pesa cero, quitarlo deja un camino de s a v con el mismo costo y menos aristas. Si pesa más que cero, quitarlo deja un camino más barato, y entonces el original no era el más corto. En los dos casos hay un camino más corto sin vértices repetidos, y por eso tiene a lo sumo |V| − 1 aristas: es la razón de que |V| − 1 rondas de Bellman-Ford alcancen.