Two problems in the search of metric characteristics on weighted undirected graphs with non-negative edge weights are being considered. The first problem: a weighted undirected graph with non-negative edge weight is given. The radius, diameter and at least one center and one pair of peripheral vertices of the graph are to be found. In the second problem we have additionally calculated the distances matrix. For the problems being considered, we proposed fast search algorithms which use only small fraction of graph's vertices for the search of the metric characteristics. The proposed algorithms have been compared to other popular methods of solving problems considered on various inputs.
* In a case where the distance matrix of a graph is unknown, the most common method of searching for the graph's metric characteristics is to solve the all-pairs shortest path problem (APSP). Most of the algorithms solving APSP problem aren't universal and they show a good solution speed for graphs only with a certain set of properties. In particular, there are algorithms for sparse graphs @cite_2 , for graphs with bounded integer edge weights @cite_6 etc. Although the complexity of solving APSP gradually decreases with the invention of new algorithms, this approach for the search of metric characteristics of weighted graphs still remains unpractical for graphs with a large number of vertices .
@cite_6 @cite_2
1988067232 2049500052 1823654214 1970052762
In the recent past, there has been considerable progress in devising algorithms for the all-pairs shortest paths (APSP) problem running in time significantly smaller than the obvious time bound of O(n3). Unfortunately, all the new algorithms are based on fast matrix multiplication algorithms that are notoriously impractical. Our work is motivated by the goal of devising purely combinatorial algorithms that match these improved running times. Our results come close to achieving this goal, in that we present algorithms with a small additive error in the length of the paths obtained. Our algorithms are easy to implement, have the desired property of being combinatorial in nature, and the hidden constants in the running time bound are fairly small. Our main result is an algorithm which solves the APSP problem in unweighted, undirected graphs with an additive error of 2 in time @math . This algorithm returns actual paths and not just the distances. In addition, we give more efficient algorithms with running time @math for the case where we are only required to determine shortest paths between k specified pairs of vertices rather than all pairs of vertices. The starting point for all our results is an @math algorithm for distinguishing between graphs of diameter 2 and 4, and this is later extended to obtaining a ratio 2 3 approximation to the diameter in time @math . Unlike in the case of APSP, our results for approximate diameter computation can be extended to the case of directed graphs with arbitrary positive real weights on the edges. We present two new algorithms for solving the All Pairs Shortest Paths (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms.The first algorithm solves the APSP problem for weighted directed graphs in which the edge weights are integers of small absolute value in O(n2+μ) time, where μ satisfies the equation ω(1, μ, 1) = 1 + 2μ and ω(1, μ, 1) is the exponent of the multiplication of an n × nμ matrix by an nμ × n matrix. Currently, the best available bounds on ω(1, μ, 1), obtained by Coppersmith, imply that μ 0 is an error parameter and W is the largest edge weight in the graph, after the edge weights are scaled so that the smallest non-zero edge weight in the graph is 1. It returns estimates of all the distances in the graph with a stretch of at most 1 + e. Corresponding paths can also be found efficiently. We show that the all pairs shortest paths (APSP) problem for undirected graphs with integer edge weights taken from the range 1, 2, ..., M can be solved using only a logarithmic number of distance products of matrices with elements in the range (1, 2, ..., M). As a result, we get an algorithm for the APSP problem in such graphs that runs in O (Mn sup spl omega ) time, where n is the number of vertices in the input graph, M is the largest edge weight in the graph, and spl omega <2.376 is the exponent of matrix multiplication. This improves, and also simplifies, an O (M sup ( spl omega +1) 2 n sup spl omega ) time algorithm of Galil and Margalit (1997). The authors have solved the all pairs shortest distances (APSD) problem for graphs with integer edge lengths. Our algorithm is subcubic for edge lengths of small (?M) absolute value. In this paper we show how to transform these algorithms to solve the all pairs shortest paths (APSP), in the same time complexity, up to a polylogarithmic factor. Forn=|V| the number of vertices,Mthe bound on edge length, and?the exponent of matrix multiplication, we get the following results: 1. A directed nonnegative APSP(n, M) algorithm which runs inO(T(n, M)) time, where T(n, m)= 2. An undirected APSP(n, M) algorithm which runs inO(M(?+1) 2n?log(Mn)) time. 3. A general APSP(n, M) algorithm which runs inO((Mn)(3+?) 2).