Caminos y algoritmos elementales en redes

En la red del dibujo, los números son costes declarados. El coste de un recorrido es la suma de los pesos que utiliza, contando cada uso. Si no hay pesos, su longitud suele ser el número de aristas. Elegir menos pasos no asegura gastar menos.

La distancia mínima busca el menor coste entre recorridos admitidos. Con pesos no negativos, si el destino es alcanzable existe un camino simple óptimo: quitar un ciclo no aumenta el coste. Si no se puede llegar, usamos ∞ como señal de inaccesibilidad, no como el peso de un recorrido encontrado.

BFS, búsqueda por anchura, empieza en nivel cero y descubre primero los vecinos, luego quienes están a dos aristas, y así sucesivamente. Una cola atiende los vértices en orden de llegada. Guardamos un predecesor al descubrir cada uno para reconstruir su primer camino.

Ese primer descubrimiento minimiza el número de aristas: ningún nivel posterior puede ofrecer menos pasos. DFS, búsqueda por profundidad, continúa por una rama hasta no poder avanzar y retrocede; usa pila o recursión. Explora conectividad, pero su primer camino encontrado no tiene por qué ser el más corto.

Para pesos no negativos, Dijkstra inicia d(A)=0 y las demás etiquetas en ∞. Una etiqueta finita es el coste de una ruta ya descubierta. En cada paso fijamos el vértice pendiente de menor etiqueta y probamos pasar por él hacia sus vecinos.

Relajar una arista u−v significa comparar d(v) con d(u)+peso(u,v). Si esta última suma es menor, actualizamos la etiqueta y su predecesor. Una etiqueta provisional puede mejorar. Podemos terminar cuando se fija el destino, no cuando se descubre por primera vez.

Al fijar la menor etiqueta pendiente, una ruta alternativa que pasa por otro vértice todavía pendiente no puede mejorarla: llegar a ese otro vértice no cuesta menos y las aristas restantes no reducen el coste. Ese argumento usa que todos los pesos sean no negativos.

Con pesos negativos se necesita otro método, como Bellman-Ford, y revisar ciclos negativos. Si se puede alcanzar un ciclo de coste negativo y luego el destino, repetirlo abarata sin límite y no existe coste mínimo finito entre recorridos que permiten repeticiones. En no dirigidos una arista negativa ya permite una ida y vuelta de coste negativo.

En un grafo no dirigido conexo, un árbol generador mínimo conecta todos los vértices sin ciclos y minimiza la suma de las aristas elegidas. Tiene n−1 aristas. Esa pregunta es distinta de conservar las rutas más baratas desde un origen a cada destino.

Kruskal ordena aristas por peso y añade cada una solo si une componentes distintas, evitando ciclos. Prim empieza con un vértice y añade la arista más barata que sale del árbol actual hacia un vértice nuevo. Ambos admiten empates y pueden producir árboles mínimos diferentes.

Un corte divide los vértices en dos grupos no vacíos. Una arista de peso mínimo que cruza el corte puede formar parte de algún árbol mínimo. Si un árbol mínimo no la contiene, añadirla crea un ciclo; quitamos de ese ciclo otra arista que cruza el mismo corte y no pesa menos.

Seguimos conectados y el coste no aumenta.

Para conservar las elecciones anteriores, usamos cortes que no separan ninguna arista ya elegida. Prim toma el corte entre su árbol y el resto; Kruskal puede usar una componente actual y las demás. Elegir simplemente las n−1 aristas globalmente más baratas sin evitar ciclos no ofrece esa garantía.

Si el grafo es desconectado, Kruskal produce un bosque mínimo, no un árbol que conecte todo.

Para un grafo finito no dirigido con aristas, todas ellas deben estar en una misma componente para poder recorrerlas juntas; los vértices aislados no estorban. Hay recorrido euleriano cerrado si todos los grados son pares, y abierto con extremos distintos si exactamente dos grados son impares.

Al entrar y salir se emparejan incidencias; los extremos abiertos dejan una sin pareja cada uno.

La suficiencia se construye enlazando recorridos cerrados hasta agotar las aristas; con dos impares se puede añadir temporalmente una conexión entre ellos y después cortarla. Un camino hamiltoniano visita cada vértice una vez; un ciclo hamiltoniano además vuelve al inicio. La prueba de paridad para Euler no decide ese problema.

Primero decidimos si buscamos pocos pasos, bajo coste, conectar toda la red o usar cada conexión una vez. Después comprobamos pesos, sentidos y conexión. La misma red puede dar respuestas distintas a esas preguntas, sin que ninguna de ellas sustituya a las otras.

Una ruta se entrega con su secuencia, suma de pesos y garantía de mínimo. Un árbol mínimo necesita además conexión y ausencia de ciclos. Con listas de adyacencia, BFS y DFS revisan un número de datos proporcional a n+m, escrito O(n+m): n vértices y m aristas.

Dijkstra y los algoritmos de árboles añaden selección por prioridad u ordenación según la implementación.