Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

All-Pairs-Shortest-Paths Algorithm in Real Life

DZone's Guide to

All-Pairs-Shortest-Paths Algorithm in Real Life

·
Free Resource

I got a phone call from a colleague the other day asking for advice on a live consulting session at a client site. The problem description (amended to prevent information disclosure) went something like this:

We’re implementing a service that manages a set of physical backup devices. There is a set of conveyor belts with intersections and robot arms that manipulate backup tapes across the room. The service gets requests such as “transfer a fresh tape X from storage cabinet 13 to backup cabinet 89, and make sure to pass through formatting computer C or D”.

When the system starts, we calculate all shortest routes from every cabinet to every other cabinet, including special requests such as going through a particular computer. This information is stored in a large hashtable indexed by route descriptions and with routes as values.

System startup with 1,000 nodes and 250 intersections takes more than 30 minutes, and memory consumption reaches a peak of approximately 5GB. This is not acceptable.

This is the classical All-Pairs-Shortest-Paths problem on graphs. We need to find efficiently the shortest path from every vertex to every other vertex, and to store this information in a compact form; the naive solution of finding and storing every possible route using DFS or similarly simple graph searches will not yield acceptable results.

First, observe that there is no need to store route information for nodes that are not intersections. If the only edge from A is to B and the only edge from B is to C, then the route A—>B—>C does not require three pieces of data to be stored—when reaching B, there is no choice where to proceed. In other words, the nodes of our graph should be only the intersections, vertices that have fan-out higher than 2.

Next, note that the additional constraints on a route don’t pose any additional difficulty. If we need the shortest path from A to B going through C, then we really need the shortest path from A to C and then the shortest path from C to B.*

Now we’re ready to discuss the algorithm itself (Floyd-Warshall algorithm). It uses an idea very similar to the previous paragraph—if we are looking for the shortest path from A to B, then suppose this path contains a vertex V. The shortest path from A to B that goes through V consists of the shortest path from A to V and the shortest path from V to B; this is the basis of a recursive formula that enumerates the possible paths. What we need to do is consider all possibilities for V—all possible intermediate vertices. One way to do this is to number the vertices from 1 to n. Now, we can use the following recursive formula for SP(i, j, k), the length/cost** of the shortest path from vertex i to vertex j and using only the vertices 1,…,k:

SP(i, j, k) = min { SP(i, j, k-1), SP(i, k, k-1) + SP(k, j, k-1) }

(If there is an edge from i to j, we also need to consider this as a possibility in the minimum calculation.)

Finding all values of SP(i, j, k) for all the vertices and values of k from 1 to n will yield the costs of the shortest paths between every two vertices in the graph. For example, the cost of the shortest path from i to j is given by finding the minimum of SP(i, j, k) for all values of k.

Although this recursive formula looks very expensive—there are three recursive calls at each level, which leads to exponential running time—we can employ memoization for the recursive calls, i.e. store somewhere the intermediate return values of SP instead of calculating them over and over again. The amount of storage required for storing these results (naively) is n3, which is pretty bad. However, it’s fairly obvious that we don’t actually need SP(i, j, k) for all values of k—we need at each iteration (of k) to store only the minimum value obtained so far, bringing down the amount of storage to n2, which is downright amazing.

What’s even more amazing is the algorithm’s running time—all we need is n3 iterations and we have the cost of the shortest path between every two vertices in the graph!

What about storing the path itself? This is a trivial modification to the algorithm—we can use an additional matrix of size n2, and store in it for each pair (i, j) the vertex x to which we should proceed if we want to find the shortest path*** from i to j.

Translating this thing to C# is easy, and so is reconstructing the path given the data described above.

short[] vertices = g.Vertices.ToArray();
int N = vertices.Length;
_costs = new float[N,N];
_next = new short[N,N];
for (short i = 0; i < N; ++i)
{
for (short j = 0; j < N; ++j)
{
_costs[i, j] = g.EdgeCost(i, j);
if (!float.IsPositiveInfinity(_costs[i, j]))
_next[i, j] = -1;//Marker for direct edge
}
}
for (short k = 0; k < N; ++k)
{
for (short i = 0; i < N; ++i)
{
for (short j = 0; j < N; ++j)
{
if (_costs[i,k] + _costs[k,j] < _costs[i,j])
{
_costs[i, j] = _costs[i, k] + _costs[k, j];
_next[i, j] = k;
}
}
}
}
public string GetPath(short src, short dst)
{
if (float.IsPositiveInfinity(_costs[src, dst]))
return "<no path>";
short intermediate = _next[src, dst];
if (intermediate == -1) //Marker for direct edge
{
return "->"; //Direct path
}
return GetPath(src, intermediate) +
intermediate +
GetPath(intermediate, dst);
}

On my desktop PC, with an average fan-out of 3 edges from each node and 300 nodes, constructing the full set of paths took 3 seconds. Spitting out 100,000 paths took 120 milliseconds. The memory utilization was 600 KB, including storage for the graph itself.

There’s plenty of additional optimization to do here—and indeed there are graph libraries like QuickGraph that thrive on implementing and optimizing such algorithms—but in view of the above results, I felt no need to explore these additional options.

 


* If there were a path P from A to B going through C that did not use Q1, the shortest path from A to C and then Q2, the shortest path from C to B, then we can break P into two parts—P1, the part of P from A to C and P2, the part of P from C to B. If P1 is not Q1, then we can improve P by replacing P1 by Q1; similarly, if P2 is not Q2, then we can improve P by replacing P2 by Q2. In either case, this is a contradiction to the assumption that P was the shortest path.

** It’s trivial to adapt the algorithm so that it works for weighted edges, and indeed in our case it may be necessary to accommodate for conveyors that consume additional energy, conveyors that become packed, etc. by assigning them a weight function.

*** Again, we use the property that every path from i to j through x uses the shortest path from i to x and the shortest path from x to j.

Topics:

Published at DZone with permission of Sasha Goldshtein, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}