Shortest Paths In Unweighed Graphs

When dealing with shortest paths in weighed or unweighed graphs, one may solve one-to-one, one-to-all or all-to-all instances. But the known algorithms compute one single shortest path of the considered instance. This article describes a new algorithm (patent pending) designed to compute all the shortest paths between two vertices of a directed, strongly connected and unweighed graph G, containing v vertices and a arcs. The purpose of this article is to propose an efficient one-to-one shortest path algorithm in unweighed graphs... The technique allows for instance the computations of all shortest paths between any two vertices in a graph G containing 10, 000, 000 vertices and 500, 000, 000 arcs in a mean time of 0.3 second on an average single processor computer. This article describes the algorithm, gives the proof of the complexity and describes some experimentations.ou