We consider the following optimization problems of directed graphs.
1. Given link costs taking values in a set endowed with ``less than'' relation and an ``addition'' operation, find an optimal spanning tree.
2. Given link costs (nonnegative real numbers) and additional constraints (nonnegative real numbers), find a path from a given source to a given destination that has minimal cost and satisfies all the constraints.
We provide optimal algorithms for both problems.
Regarding Problem 1, special cases of the proposed algorithm provide Edmond's algorithm [Edm67] and a algorithm for the bottleneck arborescence algorithm [GT88] that appears to be new. The setup provides also a polynomial time algorithm for the lexicographically optimal arborescence problem.
Problem 2 is known to be NP-complete. However, polynomial approximation algorithms exist [LR01]. The latter algorithms are based on the Dynamic Programming equation related to Problem 2. We propose an algorithm which exploits the properties of the dynamic programming functions related with each node, to provide optimal algorithms that can be considered as generalizations of Dijkstra's algorithm. The performance of these algorithms depends mainly on the number of function discontinuities, which is usually not very large, and as a result the running time is very satisfactory for graphs of fairly large size.
Back to the Index