Problema de la ruta más ancha
En los algoritmos de grafos , el problema de la ruta más ancha es el problema de encontrar una ruta entre dos vértices designados en un gráfico ponderado , maximizando el peso del borde de peso mínimo en la ruta. El problema del camino más ancho también se conoce como el problema del camino de máxima capacidad . Es posible adaptar la mayoría de los algoritmos de la ruta más corta para calcular las rutas más anchas, modificándolos para usar la distancia del cuello de botella en lugar de la longitud de la ruta. [1] Sin embargo, en muchos casos son posibles algoritmos incluso más rápidos.
Por ejemplo, en un gráfico que representa conexiones entre enrutadores en Internet , donde el peso de un borde representa el ancho de banda de una conexión entre dos enrutadores, el problema de la ruta más ancha es el problema de encontrar una ruta de extremo a extremo entre dos Internet. nodos que tiene el máximo ancho de banda posible. [2] El peso de borde más pequeño en esta ruta se conoce como capacidad o ancho de banda de la ruta. Además de sus aplicaciones en el enrutamiento de redes, el problema de la ruta más amplia también es un componente importante del método de Schulze para decidir el ganador de una elección de múltiples vías, [3] y se ha aplicado a la composición digital , [4] análisis de vías metabólicas , [5] y cálculo de flujos máximos . [6]
Un problema estrechamente relacionado, el problema de la ruta minimax o el problema de la ruta más corta de cuello de botella, pregunta por la ruta que minimiza el peso máximo de cualquiera de sus bordes. Tiene aplicaciones que incluyen la planificación del transporte . [7] Cualquier algoritmo para el problema de la ruta más ancha puede transformarse en un algoritmo para el problema de la ruta minimax, o viceversa, invirtiendo el sentido de todas las comparaciones de peso realizadas por el algoritmo, o de manera equivalente reemplazando cada peso de borde por su negación. .
En un grafo no dirigido , el camino más ancho se puede encontrar como el camino entre los dos vértices en el árbol de expansión máxima del gráfico, y el camino minimax se puede encontrar como el camino entre los dos vértices en el árbol de expansión mínimo. [8] [9] [10]
En cualquier gráfico, dirigido o no dirigido, existe un algoritmo sencillo para encontrar la ruta más ancha una vez que se conoce el peso de su arista de peso mínimo: simplemente elimine todas las aristas más pequeñas y busque cualquier ruta entre las aristas restantes utilizando la búsqueda primero en amplitud o en profundidad primera búsqueda . Basado en esta prueba, también existe un algoritmo de tiempo lineal para encontrar una ruta s - t más ancha en un gráfico no dirigido, que no usa el árbol de expansión máximo. La idea principal del algoritmo es aplicar el algoritmo de búsqueda de caminos en tiempo lineal a la medianapeso de borde en el gráfico, y luego eliminar todos los bordes más pequeños o contraer todos los bordes más grandes según si existe o no una ruta, y repetir en el gráfico más pequeño resultante. [9] [11] [12]
Fernández, Garfinkel y Arbiol (1998) utilizan caminos más cortos de cuello de botella no dirigidos para formar fotografías aéreas compuestas que combinan múltiples imágenes de áreas superpuestas. En el subproblema al que se aplica el problema del camino más ancho, ya se han transformado dos imágenes en un sistema de coordenadas común ; la tarea restante es seleccionar una costura, una curva que pasa por la región de superposición y divide una de las dos imágenes de la otra. Los píxeles de un lado de la costura se copiarán de una de las imágenes y los píxeles del otro lado de la costura se copiarán de la otra imagen. A diferencia de otros métodos de composición que promedian los píxeles de ambas imágenes, esto produce una imagen fotográfica válida de cada parte de la región que se está fotografiando. Ponderan los bordes de un gráfico de cuadrícula.mediante una estimación numérica de cuán visualmente aparente sería una costura a través de ese borde, y encuentre el camino más corto de cuello de botella para estos pesos. Usar esta ruta como la unión, en lugar de una ruta más corta más convencional, hace que su sistema encuentre una unión que es difícil de discernir en todos sus puntos, en lugar de permitirle sacrificar una mayor visibilidad en una parte de la imagen por una menor. visibilidad en otros lugares. [4]
