Problema del camino más ancho

En algoritmos de grafos , el problema del camino más ancho consiste en encontrar un camino entre dos vértices designados en un grafo ponderado , maximizando el peso de la arista de menor peso en dicho camino. Este problema también se conoce como el problema del camino de máxima capacidad . Es posible adaptar la mayoría de los algoritmos de camino más corto para calcular los caminos más anchos, modificándolos para que utilicen la distancia del cuello de botella en lugar de la longitud del camino. ^{[ 1 ]} Sin embargo, en muchos casos, existen algoritmos aún más rápidos.

Por ejemplo, en un grafo que representa las conexiones entre enrutadores en Internet , donde el peso de una arista representa el ancho de banda de una conexión entre dos enrutadores, el problema de la ruta más ancha consiste en encontrar una ruta de extremo a extremo entre dos nodos de Internet que tenga el máximo ancho de banda posible. ^{[ 2 ]} El peso de arista más pequeño en esta ruta se conoce como la 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 ancha también es un componente importante del método Schulze para decidir el ganador de una elección múltiple, ^{[ 3 ]} y se ha aplicado a la composición digital , ^{[ 4 ]} el análisis de rutas metabólicas , ^{[ 5 ]} y el cálculo de flujos máximos . ^{[ 6 ]}

Un problema estrechamente relacionado, el problema del camino minimax o problema del camino más corto en un cuello de botella, busca el camino que minimice el peso máximo de cualquiera de sus aristas. Tiene aplicaciones que incluyen la planificación del transporte . ^{[ 7 ]} Cualquier algoritmo para el problema del camino más ancho puede transformarse en un algoritmo para el problema del camino minimax, o viceversa, invirtiendo el sentido de todas las comparaciones de peso realizadas por el algoritmo, o equivalentemente reemplazando cada peso de arista por su negación.

In an undirected graph, a widest path may be found as the path between the two vertices in the maximum spanning tree of the graph, and a minimax path may be found as the path between the two vertices in the minimum spanning tree.^[8][9][10] It follows immediately from this equivalence that all pairs widest paths in an ${\displaystyle n}$-vertex undirected graph can be computed in time ${\displaystyle O(n^{2})}$.^[11]

In any graph, directed or undirected, there is a straightforward algorithm for finding a widest path once the weight of its minimum-weight edge is known: simply delete all smaller edges and search for any path among the remaining edges using breadth-first search or depth-first search. Based on this test, there also exists a linear timealgorithm for finding a widest s-t path in an undirected graph, that does not use the maximum spanning tree. The main idea of the algorithm is to apply the linear-time path-finding algorithm to the median edge weight in the graph, and then either to delete all smaller edges or contract all larger edges according to whether a path does or does not exist, and recurse in the resulting smaller graph.^[9][12][13]

Fernández, Garfinkel & Arbiol (1998) use undirected bottleneck shortest paths in order to form compositeaerial photographs that combine multiple images of overlapping areas. In the subproblem to which the widest path problem applies, two images have already been transformed into a common coordinate system; the remaining task is to select a seam, a curve that passes through the region of overlap and divides one of the two images from the other. Pixels on one side of the seam will be copied from one of the images, and pixels on the other side of the seam will be copied from the other image. Unlike other compositing methods that average pixels from both images, this produces a valid photographic image of every part of the region being photographed. They weigh the edges of a grid graph by a numeric estimate of how visually apparent a seam across that edge would be, and find a bottleneck shortest path for these weights. Using this path as the seam, rather than a more conventional shortest path, causes their system to find a seam that is difficult to discern at all of its points, rather than allowing it to trade off greater visibility in one part of the image for lesser visibility elsewhere.^[4]

Una solución al problema de la ruta minimax entre las dos esquinas opuestas de un grafo de cuadrícula puede utilizarse para hallar la distancia de Fréchet débil entre dos cadenas poligonales . En este caso, cada vértice del grafo de cuadrícula representa un par de segmentos de línea, uno de cada cadena, y el peso de una arista representa la distancia de Fréchet necesaria para pasar de un par de segmentos a otro. ^{[ 14 ]}

Si todos los pesos de las aristas de un grafo no dirigido son positivos , entonces las distancias minimax entre pares de puntos (los pesos máximos de las aristas de los caminos minimax) forman una ultramétrica ; recíprocamente, todo espacio ultramétrico finito proviene de distancias minimax de esta manera. ^{[ 15 ]} Una estructura de datos construida a partir del árbol de expansión mínima permite consultar la distancia minimax entre cualquier par de vértices en tiempo constante por consulta, utilizando consultas del ancestro común más bajo en un árbol cartesiano . La raíz del árbol cartesiano representa la arista más pesada del árbol de expansión mínima, y ​​los hijos de la raíz son árboles cartesianos construidos recursivamente a partir de los subárboles del árbol de expansión mínima formados al eliminar la arista más pesada. Las hojas del árbol cartesiano representan los vértices del grafo de entrada, y la distancia minimax entre dos vértices es igual al peso del nodo del árbol cartesiano que es su ancestro común más bajo. Una vez que las aristas del árbol de expansión mínima se han ordenado, este árbol cartesiano se puede construir en tiempo lineal. ^{[ 16 ]}

En los grafos dirigidos , no se puede utilizar la solución del árbol de expansión máxima. En su lugar, se conocen varios algoritmos diferentes; la elección del algoritmo a utilizar depende de si el vértice de inicio o de destino de la ruta es fijo, o si se deben encontrar rutas para muchos vértices de inicio o de destino simultáneamente.

También se ha considerado una variante del problema de la ruta minimax para conjuntos de puntos en el plano euclidiano . Al igual que en el problema del grafo no dirigido, este problema de la ruta minimax euclidiana se puede resolver eficientemente encontrando un árbol de expansión mínima euclidiana : cada ruta en el árbol es una ruta minimax. Sin embargo, el problema se complica cuando se desea una ruta que no solo minimice la longitud de salto, sino que también, entre rutas con la misma longitud de salto, minimice o aproxime la longitud total de la ruta. La solución se puede aproximar utilizando expansores geométricos . ^{[ 22 ]}

En teoría de números , el problema sin resolver del foso gaussiano plantea si las trayectorias minimax en los números primos gaussianos tienen una longitud minimax acotada o no acotada. Es decir, ¿existe una constante B tal que, para cada par de puntos p y q en el conjunto infinito de puntos euclidianos definido por los primos gaussianos, la trayectoria minimax en los primos gaussianos entre p y q tenga una longitud de arista minimax como máximo B ? ^{[ 23 ]}