Widest path problem
For instance, in a graph that represents connections between routers in the Internet, where the weight of an edge represents the bandwidth of a connection between two routers, the widest path problem is the problem of finding an end-to-end path between two Internet nodes that has the maximum possible bandwidth.
As well as its applications in network routing, the widest path problem is also an important component of the Schulze method for deciding the winner of a multiway election,[3] and has been applied to digital compositing,[4] metabolic pathway analysis,[5] and the computation of maximum flows.
Based on this test, there also exists a linear time algorithm for finding a widest s-t path in an undirected graph, that does not use the maximum spanning tree.
[9][12][13] Fernández, Garfinkel & Arbiol (1998) use undirected bottleneck shortest paths in order to form composite aerial photographs that combine multiple images of overlapping areas.
[4] A solution to the minimax path problem between the two opposite corners of a grid graph can be used to find the weak Fréchet distance between two polygonal chains.
The all-pairs widest path problem has applications in the Schulze method for choosing a winner in multiway elections in which voters rank the candidates in preference order.
[18] To compute the widest path widths for all pairs of nodes in a dense directed graph, such as the ones that arise in the voting application, the asymptotically fastest known approach takes time O(n(3+ω)/2) where ω is the exponent for fast matrix multiplication.
[19] Instead, the reference implementation for the Schulze method uses a modified version of the simpler Floyd–Warshall algorithm, which takes O(n3) time.
[3] For sparse graphs, it may be more efficient to repeatedly apply a single-source widest path algorithm.
The key idea behind the speedup over a conventional version of Dijkstra's algorithm is that the sequence of bottleneck distances to each vertex, in the order that the vertices are considered by this algorithm, is a monotonic subsequence of the sorted sequence of edge weights; therefore, the priority queue of Dijkstra's algorithm can be implemented as a bucket queue: an array indexed by the numbers from 1 to m (the number of edges in the graph), where array cell i contains the vertices whose bottleneck distance is the weight of the edge with position i in the sorted order.
By using a minimax path, where the weight of an edge is the maximum travel time from a point on the edge to the farthest possible service call, one can plan a route that minimizes the maximum possible delay between receipt of a service call and arrival of a responding vehicle.
[7] Ullah, Lee & Hassoun (2009) use maximin paths to model the dominant reaction chains in metabolic networks; in their model, the weight of an edge is the free energy of the metabolic reaction represented by the edge.
[20] In a model of computation where each edge weight is a machine integer, the use of repeated bisection in this algorithm can be replaced by a list-splitting technique of Han & Thorup (2002), allowing S to be split into O(√m) smaller sets Si in a single step and leading to a linear overall time bound.
[21] A variant of the minimax path problem has also been considered for sets of points in the Euclidean plane.
