Levitic Algorithm

The Levit 's algorithm, an algorithm on graphs , finds the shortest distance from one of the vertices of the graph to all the others. The algorithm also works for graphs with negative weight edges . The algorithm is widely used in programming and technology.

Content

Task

Examples

Option 1. Given the network of highways connecting the city of Moscow region. Some roads are one-way. Find the shortest way from the city of Moscow to each city of the region (if you can only move along the roads).

Option 2. There is a certain number of flights between the cities of the world, for everyone the cost is known. The cost of the flight from A to B may not be equal to the cost of the flight from B to A. Find the route of the minimum cost (possibly with transfers) from Copenhagen to Barnaul .

Formal definition

Given a weighted oriented ^[1] graph $G(V,E)$ ${\ displaystyle G (V, E)}$ without loops . Find shortest paths from some vertex $a$ ${\ displaystyle a}$ count $G$ ${\ displaystyle G}$ to all the other vertices of this graph.

Algorithm

Below is a popular and effective implementation of the modified Levit's algorithm from the site e-maxx.ru on special graphs. Its difference from the "canonical" version is to add an item to the queue $M1$ ${\ displaystyle M1}$ at the beginning, not at the end. This allows you to achieve gains in some graphs, however, leads to an exponential work time in the worst case (see the “Complexity” section).

Legend

$N$ ${\ displaystyle N}$ - many vertices of the graph
$M$ ${\ displaystyle M}$ - many edges of the graph
$g[ij]$ ${\ displaystyle g [ij]}$ - weight (length) of an edge $i j$ ${\ displaystyle ij}$
$s$ ${\ displaystyle s}$ - the vertex, the distances from which are sought, that is, the starting vertex.
$d[i]$ ${\ displaystyle d [i]}$ Is the current shortest path from the top $s$ ${\ displaystyle s}$ to the top $i$ ${\ displaystyle i}$
$p[i]$ ${\ displaystyle p [i]}$ Is the vertex preceding the vertex $i$ ${\ displaystyle i}$ in the shortest way from the top $s$ ${\ displaystyle s}$ before $i$ ${\ displaystyle i}$ .
$M0$ ${\ displaystyle M0}$ - vertices, the distance to which has already been calculated (but, possibly, not definitively);
$M1$ ${\ displaystyle M1}$ - vertices, the distance to which is calculated;
$M2$ ${\ displaystyle M2}$ - vertices, the distance to which has not yet been calculated.
$state[i]$ ${\ displaystyle state [i]}$ - stores the number of the set to which the vertex i belongs.

Code

Immediately it is necessary to stipulate the fact that the code below is not fully functional, since the structure of the graph is not specified (in any way). As a result, (by default) there is a situation in which there is a graph consisting of ten (default value) isolated vertices, and the shortest path is searched from the vertex with index 1 to the vertex with index 3 (default values).

  #include <iostream> 
 // for the pair structure:
 #include <utility> 
 #include <vector> 
 #include <deque> 
 // for the INT_MAX value:
 #include <climits> 
 // for the reverse function:
 #include <algorithm> 

 using namespace std ;

 typedef pair < int , int > edge ;
 typedef vector < vector < edge >> graph ;

 const int INFINITY = INT_MAX ;

 // Default values for the operation of the algorithm (the number of graph vertices, the indices of the initial and final vertices of the path)
 int defaultNumber = 10 , 
     defaultStart = 1 , 
     defaultFinish = 3 ;

 int main ()
 {
     int numberOfVertices = defaultNumber ,  
         startVertex = defaultStart , 
	 finishVertex = defaultFinish ;

     graph g ( numberOfVertices );
    
	 // Here we read the structure of the graph (from somewhere, for example, from a file).
	 // By the way, the dimension and the number of vertices for the search is likely
	 // must be obtained from the same source.

     vector < int > d ( numberOfVertices , INFINITY );
     d [ startVertex ] = 0 ;
    
     vector < int > state ( numberOfVertices , 2 );
     state [ startVertex ] = 1 ;
    
     deque < int > q ;
     q .  push_back ( startVertex );
    
     vector < int > p ( numberOfVertices , - 1 );

     while ( ! q . empty ())
     {
         int vertex = q .  front ();  
         q .  pop_front ();
         state [ vertex ] = 0 ;
         for ( size_t i = 0 ; i < g [ vertex ]. size (); ++ i )
         {
             int to = g [ vertex ] [ i ].  first , 
                 length = g [ vertex ] [ i ].  second ;
             if ( d [ to ] > d [ vertex ] + length )
             {
                 d [ to ] = d [ vertex ] + length ;
                 if ( state [ to ] == 2 )
                     q .  push_back ( to );
                 else if ( state [ to ] == 0 )
                     q .  push_front ( to );
                 p [ to ] = vertex ;
                 state [ to ] = 1 ;
             }
         }
     }
     if ( p [ finishVertex ] == - 1 )
     {
         cout << "No solution" << endl ;
     }
     else
     {
         vector < int > path ;
         for ( int vertex = finishVertex ; vertex ! = - 1 ; vertex = p [ vertex ])
             path .  push_back ( vertex );
         reverse ( path . begin (), path . end ());
         for ( size_t i = 0 ; i < path . size (); ++ i )
             cout << path [ i ] + 1 << '' ;
     }

     // to run not from the command line (to be able to see the result)
     cin .  get ();
     return 0 ;
 }

Description

Let the array D [1..N] contain the current shortest path lengths. Initially, the array D is filled with the values “infinity”, except for D [s] = 0. Upon the completion of the algorithm, this array will contain the final shortest distances.

Let the array P [1..N] contain the current ancestors. Just like array D, array P changes gradually along the algorithm and by the end of it takes final values.

Initially, all vertices are placed in the set M2, except for the vertex V0, which is placed in the set M1.

At each step of the algorithm, we take a vertex from the set M1 (get the top element from the queue). Let V be the selected vertex. We translate this vertex into the set M0. Then we look through all edges leaving this vertex. Let T be the second end of the current edge (that is, not equal to V), and L is the length of the current edge.

If T belongs to M2, then T is transferred to the set M1 at the end of the queue. DT set equal DV + L.
If T belongs to M1, then we are trying to improve the value of DT: DT = min (DT, DV + L). The vertex T itself does not move in the queue at all.
If T belongs to M0, and if DT can be improved (DT> DV + L), then we improve DT, and return the vertex T to the set M1 by placing it at the head of the queue.

Of course, with every update of array D, the value in array P should also be updated.

Algorithm complexity

If the algorithm is incorrectly implemented, using M1 'and M1' 'decks instead of queues and adding vertices from M0 to the beginning of the deck, the algorithm will work in the worst case for exponential time ^[2] , this is not recommended. On real graphs, the algorithm has proved itself quite well: the time of its work $O(MN)$ ${\ displaystyle O (MN)}$ ^[3] .

Comparison of Dijkstra and Levit's Algorithms

In comparison with the Dijkstra method, the Levit method loses on the fact that some vertices have to be processed again, and wins on simpler algorithms for including and excluding vertices from the set M1. Experiments show that for graphs with a "geometric" origin, that is, for graphs built on the basis of transport networks and real distances, the Levit method turns out to be the fastest. He wins and the size of the program.

The Levit method also has the advantage over the Dijkstra method that it is applicable in the case of negative arc lengths (after all, “arc length” is just a name that gives us useful associations with reality). If we assume that the values of l (u) are not necessarily positive, the solution of the shortest path problem becomes much more complicated.

The first difficulty is that the simple rule of the Dijkstra method is lost to determine the finality of the calculated distance to a particular arc. This difficulty, as we shall see, is costing, albeit with some loss of method effectiveness (we have to check all the arcs leading to a given vertex).

The second difficulty is more serious: with negative lengths in the graph, contours with a negative sum of arc lengths can be found (let's call such contours “negative”). Adding to the path of the negative contour reduces the value of the objective function, and the more detours of the negative contour we add, the “better”. It is simply impossible to get rid of the infinite decrease of the minimum, but there are two ways out of a difficult situation (of course, the choice of an exit does not depend on us, but on a practical task to be solved).

To prohibit the inclusion of contours in the path, that is, to consider only simple paths, but such a ban makes the task very difficult.

In the case of negative contours, assume that the problem has no solution, and restrict ourselves to solving the problem in cases where there are no negative contours. In this case, the Levit method will give the desired optimal solution, and with some modification will allow to “catch” the negative contours.

Notes

↑ Here, a special case of a directed graph is non-oriented and mixed (“partially oriented”) graphs.
↑ Levit (modified Ford-Bellman) from e-maxx.ru works for the exhibitor. - Codeforces
↑ Algorithm of Levita - Wikonfektsy ( Neopr .) . neerc.ifmo.ru. The appeal date is December 13, 2018.

Links

Literature

B. Yu. Levit. Algorithms for finding the shortest paths on a graph. Proceedings of the Institute of Hydrodynamics SB AS USSR. Sat "Modeling of management processes". Issue 4. Novosibirsk. 1971. p. 1117–148
B. Yu. Levit, V.N. Livshits. Nonlinear network transport problems, M. Transport. 1972. p.43-61
Dijkstra E. W. A graph. // Numer. Math - Springer Science + Business Media , 1959. - Vol. 1, Iss. 1. - P. 269–271. - ISSN 0029-599X ; 0945-3245 - doi: 10.1007 / BF01386390
<a href=" https://wikidata.org/wiki/Track:Q21694527 "> </a> <a href=" https://wikidata.org/wiki/Track:Q7069670 "> </a> <a href = " https://wikidata.org/wiki/Track:Q176916 "> </a> <a href=" https://wikidata.org/wiki/Track:Q8556 "> </a>
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algorithms: construction and analysis = Introduction to Algorithms. - 2nd ed. - M .: “Williams” , 2006. - p. 1296. - ISBN 0-07-013151-1 .
Romanovsky I.V. Discrete analysis: A textbook for students specializing in applied mathematics and computer science. . - 3rd ed. - SPb. : Nevsky Dialect , 2003. - p. 221-222.
Ananias V. Levitin. Algorithms: an introduction to the development and analysis of the Aigorithms. - M .: "Williams" , 2006. - p. 189-195. - ISBN 0-201-74395-7 .

[1] Here, a special case of a directed graph is non-oriented and mixed (“partially oriented”) graphs.

[2] Levit (modified Ford-Bellman) from e-maxx.ru works for the exhibitor. - Codeforces

[3] Algorithm of Levita - Wikonfektsy ( Neopr .) . neerc.ifmo.ru. The appeal date is December 13, 2018.