## Archiv für September, 2016

September 28th, 2016

## Solving the Shortest Path Problem (2) – LEMON Graph Library

LEMON Graph Library

LEMON stands for Library for Efficient Modeling and Optimization in Networks. It is a C++ template library providing efficient implementations of common data structures and algorithms with focus on combinatorial optimization tasks connected mainly with graphs and networks.

http://lemon.cs.elte.hu/trac/lemon

I like LEMON because of its nice and simple API. There is also a mailing list which offers quick support. Its latest version 1.3.1 was updated in August 2014.

So let’s see what’s on the agenda:

1. Prerequisites
2. Populate a graph
3. Setup a shortest path solver
4. Solve it, get the cost and the path

weiterlesen »

Be the first to like.

September 24th, 2016

## 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.

https://en.wikipedia.org/wiki/Shortest_path_problem

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: