I doubt this could be an efficient way to compute a shortest path. All of this amounts to a (very inefficient) parallel implementation of an algorithm that chec

I doubt this could be an efficient way to compute a shortest path. All of this amounts to a (very inefficient) parallel implementation of an algorithm that checks whether the Bellman-Ford conditions apply to a suboptimal path, as the path is gradually improved. The Bellman-Ford condition on an arc (i,j) of a graph G constrains the difference of potential between the two nodes i and j, (y_j - y_i), to be no more than the length c_ij of the arc. When it is violated, a better path can be found by modifying the potentials. The inefficiency here lies in the random nature of these checks, which (if I correctly understood) modify. A much more intuitive algorithm is Bellman-Ford's algorithm, which works even when some arc costs are negative, while Dijkstra's algorithm, much more efficient, can only be applied on non-negative arc costs. Networks with millions of nodes (such as GPS road networks) could hardly benefit from this ant-colony algorithm, and there are already better algorithms -- see the work by Andrew Goldberg, for instance (http://www.avglab.com/andrew http://www.avglab.com/andrew).