Using Dijkstra's Algorithm with the Lemon Graph Library

2.1k views Asked by At

I have a question regarding some of the parameters necessary to run Dijkstra's algorithm from the Lemon Graph Libraries (Lemon's Dijkstra's http://lemon.cs.elte.hu/pub/tutorial/a00009.html). To run the algorithm, one would write something like dijkstra(g, length).distMap(dist).run(s,t); where g is the graph, s is that starting node and t is the destination node. My question is what is length and dist, and how are they used. Thanks!

1

There are 1 answers

0
ntg On

The way I read it, they both need to be maps, one to edge lengths (input) one to vertex distances(output),

Also check lgf_demo.cc and dijkstra_test.cc and note

Dijkstra& distMap ( DistMap & m ) [inline]

Sets the map that stores the distances of the nodes calculated by the algorithm. If you don't use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated map, of course.

Returns: (*this)


const DistMap& distMap ( ) const [inline]

Returns a const reference to the node map that stores the distances of the nodes calculated by the algorithm.

Precondition: Either run() or init() must be called before using this function.

so this is your output of Dijstra.