Abstract :
This paper introduces a symbolic (non-arithmetic) algorithm for finding all the shortest paths in a directed or undirected graph, multigraph, or pseudograph from any specified initial vertex to any specified final vertex or to all other vertices. Dubbed SASP (Symbolic Algorithm for Shortest Paths), this breadth-first backtracking algorithm is based on a syntactical representation of the edges and vertices as a grammar in Backus Naur Form. Extending the algorithm from equal-length edges to edges of arbitrary length requires the quantization of each edge length to a user-specified precision that is deemed to provide sufficient accuracy for a specific application. The formal proof of the correctness of the SASP algorithm has not yet been derived, but extensive trials under a variety of classically difficult conditions have never revealed a failure. The time complexity of the algorithm is approximately O(e log v), where e is the total number of edges and v is the total number of vertices.
