Single source shortest paths in H-minor free graphs

We present an algorithm for the Single Source Shortest Paths (SSSP) problem in directed H-minor free graphs. For every fixed H, if G is a graph with n vertices having integer edge lengths and s is a designated source vertex of G, the algorithm runs in time, where L is the absolute value of the smallest edge length. The algorithm computes the shortest paths and the distances from s to all vertices of the graph, or else provides a certificate that G is not H-minor free. Our result improves an earlier O(n1.5logL) time algorithm for this problem, which follows from a general SSSP algorithm of Goldberg.