Extremal paths in graphs

This book examines the central problem of searching for optimal paths in graphs—the search for the shortest connection from one place to another one in a city, for example. It investigates generalized versions of the Dijkstra algorithm and the Ford-Bellman algorithm. These generalized search strategies find paths with minimum or almost minimum costs even if the cost function is not computed by adding costs of the edges of a path. The book describes many types of optimal path problems including the search for optimal paths in random graphs or NP-complete optimal path problems like the Traveling Salesman Problem. It also studies structural properties of cost measures for paths in graphs; in particular, generalized versions of additivity, Bellman properties, and order preservation of cost functions.