ConstrainedShortestPath< Graph, CM, DM > Class Template Reference
[Approximation algorithms]

---

Detailed Description

template<class Graph, class CM = typename Graph:: template EdgeMap<double>, class DM = CM>
class lemon::ConstrainedShortestPath< Graph, CM, DM >

The Resource Constrained Shortest (Least Cost) Path problem is the following. We are given a directed graph with two additive weightings on the edges, referred as cost and delay. In addition, a source and a destination node s and t and a delay constraint D is given. A path p is called feasible if delay(p)<=D. Then, the task is to find the least cost feasible path. #include <lemon/csp.h>

List of all members.

Public Member Functions
	ConstrainedShortestPath (const Graph &g, const CM &ct, const DM &dl)
	Constructor.
double	cost (const Path &p) const
	Compute the cost of a path.
double	delay (const Path &p) const
	Compute the delay of a path.
Path	larac (Node s, Node t, double delta, double &lo_bo)
	Runs the LARAC algorithm.

---

Constructor & Destructor Documentation

ConstrainedShortestPath	(	const Graph &	g,
		const CM &	ct,
		const DM &	dl
	)			[inline]

Constructor

---

Member Function Documentation

Path larac	(	Node	s,
		Node	t,
		double	delta,
		double &	lo_bo
	)			[inline]

This function runs a Lagrange relaxation based heuristic to find a delay constrained least cost path.

Parameters:

	s	source node
	t	target node
	delta	upper bound on the delta

Return values:

lo_bo

a lower bound on the optimal solution

Returns:

the found path or an empty