Shortest paths in digraphs of small treewidth. Part I: Sequential algorithms

We consider the problem of preprocessing an n-vertex digraph with real edge weights so that subsequent queries for the shortest path or distance betwe en any two vertices can be efficiently answered. We give algorithms that de pend on the treewidth of the input graph. When the treewidth is a constant, our algorithms can answer distance queries in O(alpha(n)) time after O(n) preprocessing. This improves upon previously known results for the same pro blem. We also give a dyna the data structure in time O(n(beta)), for any co nstant 0 < beta < 1. Furthermore, an algorithm of independent interest is g iven: computing a shortest path tree, or finding a negative cycle in linear time.