Widest path problem
Encyclopedia
In graph algorithms, the widest path problem, also known as the bottleneck shortest path problem or the maximum capacity path problem, is the problem of finding a path
between two designated vertices
in a weighted directed graph
, maximizing the weight of the minimum-weight edge in the path.
For instance, if the graph represents connections between routers in the internet
, and 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. The weight of the minimum-weight edge is known as the capacity or bandwidth of the path. 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, and has been applied to digital compositing
, metabolic analysis, and the computation of maximum flows. It is possible to adapt most shortest path algorithms to compute widest paths, by modifying them to use the bottleneck distance instead of path length. However, in many cases even faster algorithms are possible.
A closely related problem, the minimax path problem, asks for the path that minimizes the maximum weight of any of its edges. It has applications that include transportation planning. Any algorithm for the widest path problem can be transformed into an algorithm for the minimax path problem, or vice versa, by reversing the sense of all the weight comparisons performed by the algorithm, or equivalently by replacing every edge weight by its negation.
of the graph, and a minimax path may be found as the path between the two vertices in the minimum spanning tree.
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 time algorithm
for finding a widest 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.
use undirected bottleneck shortest paths in order to form composite
aerial 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 weight the edges of a grid graph by a numeric estimate of how visually apparent a seam through that point would be; the choice of a bottleneck shortest path as the seam, rather than a more conventional shortest path, forces 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.
If all edge weights of an undirected graph are positive, then the minimax distances between pairs of points (the maximum edge weights of minimax paths) form an ultrametric; conversely every finite ultrametric space comes from minimax distances in this way. A data structure
constructed from the minimum spanning tree allows the minimax distance between any pair of vertices to be computed in constant time per distance, using lowest common ancestor
queries in a Cartesian tree
. The root of the Cartesian tree represents the heaviest minimum spanning tree edge, and the children of the root are Cartesian trees recursively
constructed from the subtrees of the minimum spanning tree formed by removing the heaviest edge. The leaves of the Cartesian tree represent the vertices of the input graph, and the minimax distance between two vertices equals the weight of the Cartesian tree node that is their lowest common ancestor. Once the minimum spanning tree edges have been sorted, this Cartesian tree can be constructed in linear time.
s, the maximum spanning tree solution cannot be used. Instead, several different algorithms are known; the choice of which algorithm to use depends on whether a start or destination vertex for the path is fixed, or whether paths for many start or destination vertices must be found simultaneously.
for choosing a winner in multiway election
s in which voters rank the candidates in preference order
. The Schulze method constructs a complete directed graph
in which the vertices represent the candidates and every two vertices are connected by an edge. Each edge is directed from the winner to the loser of a pairwise contest between the two candidates it connects, and is labeled with the margin of victory of that contest. Then the method computes widest paths between all pairs of vertices, and the winner is the candidate whose vertex has wider paths to each opponent than vice versa. The results of an election using this method are consistent with the Condorcet method
– a candidate who wins all pairwise contests automatically wins the whole election – but it generally allows a winner to be selected, even in situations where the Concorcet method itself fails. The Schulze method has been used by several organizations including the Wikimedia Foundation
.
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 where ω is the exponent for fast matrix multiplication. Using the best known algorithms for matrix multiplication, this time bound becomes . Instead, the reference implementation for the Schulze method method uses a modified version of the simpler Floyd–Warshall algorithm, which takes time. For sparse graphs, it may be more efficient to repeatedly apply a single-source widest path algorithm.
can compute the bottlenecks between a designated start vertex and every other vertex in the graph, in linear time. 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 replaced by an array indexed by the numbers from 1 to (the number of edges in the graph), where array cell contains the vertices whose bottleneck distance is the weight of the edge with position in the sorted order. This method allows the widest path problem to be solved as quickly as sorting
; for instance, if the edge weights are represented as integers, then the time bounds for integer sorting
a list of integers would apply also to this problem.
s; in their model, the weight of an edge is the free energy of the metabolic reaction represented by the edge.
Another application of widest paths arises in the Ford–Fulkerson algorithm for the maximum flow problem
. Repeatedly augmenting a flow along a maximum capacity path in the residual network of the flow leads to a small bound, , on the number of augmentations needed to find a maximum flow; here, the edge capacities are assumed to be integers that are at most . However, this analysis does not depend on finding a path that has the exact maximum of capacity; any path whose capacity is within a constant factor of the maximum suffices. Combining this approximation idea with the shortest path augmentation method of the Edmonds–Karp algorithm leads to a maximum flow algorithm with running time .
It is possible to find maximum-capacity paths and minimax paths with a single source and single destination very efficiently even in models of computation that allow only comparisons of the input graph's edge weights and not arithmetic on them. The algorithm maintains a set of edges that are known to contain the bottleneck edge of the optimal path; initially, is just the set of all edges of the graph. At each iteration of the algorithm, it splits into an ordered sequence of subsets of approximately equal size; the number of subsets in this partition is chosen in such a way that all of the split points between subsets can be found by repeated median-finding in time . The algorithm then reweights each edge of the graph by the index of the subset containing the edge, and uses the modified Dijkstra algorithm on the reweighted graph; based on the results of this computation, it can determine in linear time which of the subsets contains the bottleneck edge weight. It then replaces by the subset that it has determined to contain the bottleneck weight, and starts the next iteration with this new set . The number of subsets into which can be split increases exponentially with each step, so the number of iterations is proportional to the iterated logarithm
function, , and the total time is . 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 , allowing to be split into smaller sets in a single step and leading to a linear overall time bound.
. However, it becomes more complicated when a path is desired that not only minimizes the hop length but also, among paths with the same hop length, minimizes or approximately minimizes the total length of the path. The solution can be approximated using geometric spanner
s.
In number theory
, the unsolved Gaussian moat problem asks whether or not minimax paths in the Gaussian prime numbers
have bounded or unbounded minimax length. That is, does there exist a constant such that, for every pair of points and in the infinite Euclidean point set defined by the Gaussian primes, the minimax path in the Gaussian primes between and has minimax edge length at most ?
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
between two designated vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
in a weighted directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
, maximizing the weight of the minimum-weight edge in the path.
For instance, if the graph represents connections between routers in the internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
, and the weight of an edge represents the bandwidth
Bandwidth (computing)
In computer networking and computer science, bandwidth, network bandwidth, data bandwidth, or digital bandwidth is a measure of available or consumed data communication resources expressed in bits/second or multiples of it .Note that in textbooks on wireless communications, modem data transmission,...
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. The weight of the minimum-weight edge is known as the capacity or bandwidth of the path. As well as its applications in network routing, the widest path problem is also an important component of the Schulze method
Schulze method
The Schulze method is a voting system developed in 1997 by Markus Schulze that selects a single winner using votes that express preferences. The method can also be used to create a sorted list of winners...
for deciding the winner of a multiway election, and has been applied to digital compositing
Digital compositing
Digital compositing is the process of digitally assembling multiple images to make a final image, typically for print, motion pictures or screen display...
, metabolic analysis, and the computation of maximum flows. It is possible to adapt most shortest path algorithms to compute widest paths, by modifying them to use the bottleneck distance instead of path length. However, in many cases even faster algorithms are possible.
A closely related problem, the minimax path problem, asks for the path that minimizes the maximum weight of any of its edges. It has applications that include transportation planning. Any algorithm for the widest path problem can be transformed into an algorithm for the minimax path problem, or vice versa, by reversing the sense of all the weight comparisons performed by the algorithm, or equivalently by replacing every edge weight by its negation.
Undirected graphs
In an undirected graph, a widest path may be found as the path between the two vertices in the maximum spanning treeMinimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
of the graph, and a minimax path may be found as the path between the two vertices in the minimum spanning tree.
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 time algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for finding a widest 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
Median
In probability theory and statistics, a median is described as the numerical value separating the higher half of a sample, a population, or a probability distribution, from the lower half. The median of a finite list of numbers can be found by arranging all the observations from lowest value to...
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.
use undirected bottleneck shortest paths in order to form composite
Digital compositing
Digital compositing is the process of digitally assembling multiple images to make a final image, typically for print, motion pictures or screen display...
aerial photographs
Aerial photography
Aerial photography is the taking of photographs of the ground from an elevated position. The term usually refers to images in which the camera is not supported by a ground-based structure. Cameras may be hand held or mounted, and photographs may be taken by a photographer, triggered remotely or...
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
Image registration
Image registration is the process of transforming different sets of data into one coordinate system. Data may be multiple photographs, data from different sensors, from different times, or from different viewpoints. It is used in computer vision, medical imaging, military automatic target...
; 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 weight the edges of a grid graph by a numeric estimate of how visually apparent a seam through that point would be; the choice of a bottleneck shortest path as the seam, rather than a more conventional shortest path, forces 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.
If all edge weights of an undirected graph are positive, then the minimax distances between pairs of points (the maximum edge weights of minimax paths) form an ultrametric; conversely every finite ultrametric space comes from minimax distances in this way. A data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
constructed from the minimum spanning tree allows the minimax distance between any pair of vertices to be computed in constant time per distance, using lowest common ancestor
Lowest common ancestor
The lowest common ancestor is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants .The LCA of v and w in T is the shared ancestor of v...
queries in a Cartesian tree
Cartesian tree
In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers; it can be uniquely defined from the properties that it is heap-ordered and that a symmetric traversal of the tree returns the original sequence...
. The root of the Cartesian tree represents the heaviest minimum spanning tree edge, and the children of the root are Cartesian trees recursively
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
constructed from the subtrees of the minimum spanning tree formed by removing the heaviest edge. The leaves of the Cartesian tree represent the vertices of the input graph, and the minimax distance between two vertices equals the weight of the Cartesian tree node that is their lowest common ancestor. Once the minimum spanning tree edges have been sorted, this Cartesian tree can be constructed in linear time.
Directed graphs
In directed graphDirected graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
s, the maximum spanning tree solution cannot be used. Instead, several different algorithms are known; the choice of which algorithm to use depends on whether a start or destination vertex for the path is fixed, or whether paths for many start or destination vertices must be found simultaneously.
All pairs
The all-pairs widest path problem has applications in the Schulze methodSchulze method
The Schulze method is a voting system developed in 1997 by Markus Schulze that selects a single winner using votes that express preferences. The method can also be used to create a sorted list of winners...
for choosing a winner in multiway election
Election
An election is a formal decision-making process by which a population chooses an individual to hold public office. Elections have been the usual mechanism by which modern representative democracy operates since the 17th century. Elections may fill offices in the legislature, sometimes in the...
s in which voters rank the candidates in preference order
Preferential voting
Preferential voting is a type of ballot structure used in several electoral systems in which voters rank candidates in order of relative preference. For example, the voter may select their first choice as '1', their second preference a '2', and so on...
. The Schulze method constructs a complete directed graph
Tournament (graph theory)
A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph. That is, it is a directed graph in which every pair of vertices is connected by a single directed edge....
in which the vertices represent the candidates and every two vertices are connected by an edge. Each edge is directed from the winner to the loser of a pairwise contest between the two candidates it connects, and is labeled with the margin of victory of that contest. Then the method computes widest paths between all pairs of vertices, and the winner is the candidate whose vertex has wider paths to each opponent than vice versa. The results of an election using this method are consistent with the Condorcet method
Condorcet method
A Condorcet method is any single-winner election method that meets the Condorcet criterion, which means the method always selects the Condorcet winner if such a candidate exists. The Condorcet winner is the candidate who would beat each of the other candidates in a run-off election.In modern...
– a candidate who wins all pairwise contests automatically wins the whole election – but it generally allows a winner to be selected, even in situations where the Concorcet method itself fails. The Schulze method has been used by several organizations including the Wikimedia Foundation
Wikimedia Foundation
Wikimedia Foundation, Inc. is an American non-profit charitable organization headquartered in San Francisco, California, United States, and organized under the laws of the state of Florida, where it was initially based...
.
To compute the widest path widths for all pairs of nodes in a dense
Dense graph
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph...
directed graph, such as the ones that arise in the voting application, the asymptotically
Asymptotic computational complexity
In computational complexity theory, asymptotic computational complexity is the usage of the asymptotic analysis for the estimation of computational complexity of algorithms and computational problems, commonly associated with the usage of the big O notation....
fastest known approach takes time where ω is the exponent for fast matrix multiplication. Using the best known algorithms for matrix multiplication, this time bound becomes . Instead, the reference implementation for the Schulze method method uses a modified version of the simpler Floyd–Warshall algorithm, which takes time. For sparse graphs, it may be more efficient to repeatedly apply a single-source widest path algorithm.
Single source
If the edges are sorted by their weights, then a modified version of Dijkstra's algorithmDijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
can compute the bottlenecks between a designated start vertex and every other vertex in the graph, in linear time. 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
Priority queue
A priority queue is an abstract data type in computer programming.It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a "priority"....
of Dijkstra's algorithm can be replaced by an array indexed by the numbers from 1 to (the number of edges in the graph), where array cell contains the vertices whose bottleneck distance is the weight of the edge with position in the sorted order. This method allows the widest path problem to be solved as quickly as sorting
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
; for instance, if the edge weights are represented as integers, then the time bounds for integer sorting
Integer sorting
In computer science, integer sorting is the algorithmic problem of sorting a collection of data values by numeric keys, each of which is an integer. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numbers or text strings...
a list of integers would apply also to this problem.
Single source and single destination
suggest that service vehicles and emergency vehicles should use minimax paths when returning from a service call to their base. In this application, the time to return is less important than the response time if another service call occurs while the vehicle is in the process of returning. 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. use maximin paths to model the dominant reaction chains in metabolic networkMetabolic network
A metabolic network is the complete set of metabolic and physical processes that determine the physiological and biochemical properties of a cell...
s; in their model, the weight of an edge is the free energy of the metabolic reaction represented by the edge.
Another application of widest paths arises in the Ford–Fulkerson algorithm for the maximum flow problem
Maximum flow problem
In optimization theory, the maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum....
. Repeatedly augmenting a flow along a maximum capacity path in the residual network of the flow leads to a small bound, , on the number of augmentations needed to find a maximum flow; here, the edge capacities are assumed to be integers that are at most . However, this analysis does not depend on finding a path that has the exact maximum of capacity; any path whose capacity is within a constant factor of the maximum suffices. Combining this approximation idea with the shortest path augmentation method of the Edmonds–Karp algorithm leads to a maximum flow algorithm with running time .
It is possible to find maximum-capacity paths and minimax paths with a single source and single destination very efficiently even in models of computation that allow only comparisons of the input graph's edge weights and not arithmetic on them. The algorithm maintains a set of edges that are known to contain the bottleneck edge of the optimal path; initially, is just the set of all edges of the graph. At each iteration of the algorithm, it splits into an ordered sequence of subsets of approximately equal size; the number of subsets in this partition is chosen in such a way that all of the split points between subsets can be found by repeated median-finding in time . The algorithm then reweights each edge of the graph by the index of the subset containing the edge, and uses the modified Dijkstra algorithm on the reweighted graph; based on the results of this computation, it can determine in linear time which of the subsets contains the bottleneck edge weight. It then replaces by the subset that it has determined to contain the bottleneck weight, and starts the next iteration with this new set . The number of subsets into which can be split increases exponentially with each step, so the number of iterations is proportional to the iterated logarithm
Iterated logarithm
In computer science, the iterated logarithm of n, written n , is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1...
function, , and the total time is . 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 , allowing to be split into smaller sets in a single step and leading to a linear overall time bound.
Euclidean point sets
A variant of the minimax path problem has also been considered for sets of points in the Euclidean plane. As in the undirected graph problem, this can be solved efficiently by finding a Euclidean minimum spanning treeEuclidean minimum spanning tree
The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of n points in the plane , where the weight of the edge between each pair of points is the distance between those two points...
. However, it becomes more complicated when a path is desired that not only minimizes the hop length but also, among paths with the same hop length, minimizes or approximately minimizes the total length of the path. The solution can be approximated using geometric spanner
Geometric spanner
A geometric spanner or a k-spanner graph or a k-spanner was initially introduced as a weighted graph over a set of points as its vertices which for every pair of vertices has a path between them of weight at most k times the spatial distance between these points for a fixed k...
s.
In number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, the unsolved Gaussian moat problem asks whether or not minimax paths in the Gaussian prime numbers
Gaussian integer
In number theory, a Gaussian integer is a complex number whose real and imaginary part are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as Z[i]. The Gaussian integers are a special case of the quadratic...
have bounded or unbounded minimax length. That is, does there exist a constant such that, for every pair of points and in the infinite Euclidean point set defined by the Gaussian primes, the minimax path in the Gaussian primes between and has minimax edge length at most ?