Solving the Shortest Path Problem (1) – Intro

Shortest Path Problem

3 years later I’m back with a new article in my blog – time flies..

The Shortest Path Problem is a common problem to nearly anyone nowadays. Anyone who used a navigation system or Google Maps for finding the best route for the weekend trip has already sucessfully solved the shortest path problem.
A solution to the shortest path (in terms of distance, time or any arbitrary cost) is to find the best route from one point of a network (maybe a street network) to another.

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

There are several tools for solving this problem – even free of charge and on any platform. In the following article series I want to explore the usage and the performance of various graph libraries that offer a shortest path solver.

List of the packages I want to explore:

  • Google OR-Tools
  • LEMON Graph Library
  • Boost Graph Library (BGL)

Note: I deleted Google OR-Tools from the list, because anything with Google OR-Tools was a mess:

  • Installation first failed
    (recent Ubuntu installation package does not work – „make third_party“ gives a „no rule defined for ‚third_party'“)
  • the API is too complicated (I found callbacks hard to understand in Javascript – I really don’t want to program with callbacks in C++
  • Be the first to like.

Kommentar hinzufügen