[Lemon-user] Question about using dijkstra's algorithm

[Kovács Péter]

Hi All,

> Assuming that the other variables are declared correctly, your code
> should work. e.g:
>
> #include <lemon/smart_graph.h>
> #include <lemon/dijkstra.h>
> #include <stdio.h>
>
> using namespace lemon;
>
> int main()
> {
> SmartDigraph g;
> SmartDigraph::ArcMap<int> length(g);
> SmartDigraph::NodeMap<int> dist(g);
> SmartDigraph::Node s = g.addNode();
> SmartDigraph::Node t = g.addNode();
> SmartDigraph::Arc a = g.addArc(s,t);
> length[a] = 1;
> Dijkstra<SmartDigraph> dijkstra(g, length);
> dijkstra.distMap(dist);
> dijkstra.init();
> dijkstra.addSource(s);
> dijkstra.start();
> printf("%i\n", dist[t]);
> return 0;
> }
>
> Note, that the "dijkstra" in the first example is different from the
> "dijkstra" in the second, because the first is a function, and the
> second is an instance of the Dijkstra class.

Let me add a few notes:

1. You can use the run() function to make the code simpler:
	dijkstra.run(s);
instead of:
	dijkstra.init();
	dijkstra.addSource(s);
	dijkstra.start();
The run() function is simpler to use, while the second solution is more 
flexible, e.g. you can add more then one source node.

2. You can directly retrieve a shortest path to a given target node 
(after executing the algorithm):
	Path<SmartDigraph> p = dijkstra.path(t);
For more information about the Path structures in LEMON, see:
http://lemon.cs.elte.hu/pub/doc/1.2/a00518.html

Regards,
Peter


> More information:
> http://lemon.cs.elte.hu/pub/doc/1.1.1/a00437.html#ga6aa57523fe00e2b8fe2f5cd17dd15cea
> http://lemon.cs.elte.hu/pub/doc/1.1.1/a00087.html
>
> regards,
> Gábor
>
> On 01/04/2011 07:37 PM, Yongjia Song wrote:
>> Hi all,
>>
>> I am a new user of lemon, and I could not figure out a way to use
>> dijkstra's algorithm appropriately.
>>
>> Is there any example file for that? I can see that the documentation
>> part of dijkstra's algorithm on the website could not work.
>>
>> Basically, I use
>>
>> SmartDigraph g;
>> SmartDigraph::ArcMap<int> cap(g)
>> Dijkstra<SmartDigraph> dijkstra(g,cap)
>>
>> then I could not run either
>>   dijkstra  <http://lemon.cs.elte.hu/pub/doc/1.1.1/a00437.html#ga6aa57523fe00e2b8fe2f5cd17dd15cea>(g, cap).distMap(dist).run(s,t);
>>
>>
>> or
>>
>> dijkstra  <http://lemon.cs.elte.hu/pub/doc/1.1.1/a00437.html#ga6aa57523fe00e2b8fe2f5cd17dd15cea>.distMap(dist);
>> dijsktra.init();
>> dijkstra  <http://lemon.cs.elte.hu/pub/doc/1.1.1/a00437.html#ga6aa57523fe00e2b8fe2f5cd17dd15cea>.addSource(s);
>>
>> dijkstra  <http://lemon.cs.elte.hu/pub/doc/1.1.1/a00437.html#ga6aa57523fe00e2b8fe2f5cd17dd15cea>.start();
>>
>> Thanks,
>>
>> --
>> Sincerely:
>> Song Yongjia（宋永佳）
>>
>> Department of Industrial and Systems Engineering
>> College of Engineering, University of Wisconsin-Madison
>> 3241 Mechanical Engineering Building
>> 1513 University Avenue, Madison, WI 53706
>>
>>
>> _______________________________________________
>> Lemon-user mailing list
>> Lemon-user at lemon.cs.elte.hu
>> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>