Dijkstra's algorithm
Dijkstra's algorithm
Hi
Do you know any implementation's of Dijkstra's algoritm in GAMS?
Regards
RE: Dijkstra's algorithm
Why do you need to implement Dijkstra's Algorithm in GAMS? GAM is not a programming language. It is a modelling language. There are some types of shortest path models. You can use them to write in GAMS.
> Date: Mon, 13 Dec 2010 05:38:49 0800
> Subject: Dijkstra's algorithm
> From: laurent.franckx@vito.be
> To: gamsworld@googlegroups.com
>
> Hi
>
> Do you know any implementation's of Dijkstra's algoritm in GAMS?
>
> Regards
>
> 
> To post to this group, send email to gamsworld@googlegroups.com.
> To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.
>

To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.
Re: Dijkstra's algorithm
Sometime in December, Hakan Kutucu proposed the following:

 Why do you need to implement Dijkstra's Algorithm in GAMS? GAM is not a
 programming language. It is a modelling language. There are some types of
 shortest path models. You can use them to write in GAMS.
More to the point, Dijkstra's Algorithm is going to be implemented in the
solver the user instructs GAMs to use. So if someone is looking for a
specific algorithm implementation, they should probably consult the
documentation for the different solvers.
 John M Harrold
Re: Dijkstra's algorithm
Hi Laurent
Here is an example I implemented:
http://www.modelworks.ch/dijkstra.htm
Cheers
Renger
http://blog.modelworks.ch
On Mon, Dec 13, 2010 at 2:38 PM, Laurent Franckx wrote:
Hi
Do you know any implementation's of Dijkstra's algoritm in GAMS?
Regards

To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.

Renger van Nieuwkoop

To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.
Re: Dijkstra's algorithm
Hi
Here is an implementation of the Dijksktra algorithm:
http://www.modelworks.ch/dijkstra.htm
Cheers
Renger
http://blog.modelworks.ch
On 13 Dez., 15:58, John Harrold wrote:
> > Sometime in December, Hakan Kutucu proposed the following:
> >
> > 
> >  Why do you need to implement Dijkstra's Algorithm in GAMS? GAM is not a
> >  programming language. It is a modelling language. There are some types of
> >  shortest path models. You can use them to write in GAMS.
> >
> > More to the point, Dijkstra's Algorithm is going to be implemented in the
> > solver the user instructs GAMs to use. So if someone is looking for a
> > specific algorithm implementation, they should probably consult the
> > documentation for the different solvers.
> >
> > 
> > John M Harrold
RE: Dijkstra's algorithm
Dear Renger
Thank you for this.
Do you have any idea of the performance of this algorythm when applied to largescale problems (several thousands of origins and destinations)?
Regards
Laurent
Van: gamsworld@googlegroups.com [gamsworld@googlegroups.com] namens Renger van Nieuwkoop [rvannieuwkoop@gmail.com]
Verzonden: dinsdag 14 december 2010 9:04
Aan: gamsworld@googlegroups.com
Onderwerp: Re: Dijkstra's algorithm
Hi Laurent
Here is an example I implemented:
http://www.modelworks.ch/dijkstra.htm
Cheers
Renger
http://blog.modelworks.ch
On Mon, Dec 13, 2010 at 2:38 PM, Laurent Franckx wrote:
Hi
Do you know any implementation's of Dijkstra's algoritm in GAMS?
Regards

To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.

Renger van Nieuwkoop

To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.
This email, any attachments and the information it contains are confidential and meant only for the use of the addressee(s) only. Access to this email by anyone other than the addressee(s) is unauthorized. If you are not the intended addressee (or responsible for delivery of the message to such person), you may not use, copy, distribute or deliver to anyone this message (or any part of its contents) or take any action in reliance on it. In such case, you should destroy this message and notify the sender immediately. If you have received this email in error, please notify us immediately by email or telephone and delete the email from any computer.
All reasonable precautions have been taken to ensure no viruses are present in this email and its attachments. As our company cannot accept responsibility for any loss or damage arising from the use of this email or attachments we recommend that you subject these to your virus checking procedures prior to use.

To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.
Re: Dijkstra's algorithm
No, I switched to using igraph in R (http://cneurocvs.rmki.kfki.hu/igraph/do ... paths.html), which is quite fast..
Renger
On Mon, Dec 13, 2010 at 2:38 PM, Laurent Franckx wrote:
Hi
Do you know any implementation's of Dijkstra's algoritm in GAMS?
Regards

To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.

Renger van Nieuwkoop

To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.
Re: Dijkstra's algorithm
Replyto: gamsworld@googlegroups.com
Hi Renger,
thanks for this code. Unfortunately I found an instance in which there is something weird. In the .gms file attached, I just copied your code, changed the tmatrix, and added the origindestination pair (3,4). The shortest path I got according to this code is 354, total length 2.774. But there is another path, 38754, which has a shorter length, 2.594. Any idea why this might be happening?
By the way, thank you very much for all the help you post in this group
Fede
On Wednesday, December 15, 2010 3:28:20 PM UTC+1, Renger wrote:
No, I switched to using igraph in R (http://cneurocvs.rmki.kfki.hu/igraph/do ... paths.html), which is quite fast..
Renger
On Mon, Dec 13, 2010 at 2:38 PM, Laurent Franckx wrote:
Hi
Do you know any implementation's of Dijkstra's algoritm in GAMS?
Regards

Hi Renger,
thanks for this code. Unfortunately I found an instance in which there is something weird. In the .gms file attached, I just copied your code, changed the tmatrix, and added the origindestination pair (3,4). The shortest path I got according to this code is 354, total length 2.774. But there is another path, 38754, which has a shorter length, 2.594. Any idea why this might be happening?
By the way, thank you very much for all the help you post in this group
Fede
On Wednesday, December 15, 2010 3:28:20 PM UTC+1, Renger wrote:
No, I switched to using igraph in R (http://cneurocvs.rmki.kfki.hu/igraph/do ... paths.html), which is quite fast..
Renger
On Mon, Dec 13, 2010 at 2:38 PM, Laurent Franckx wrote:
Hi
Do you know any implementation's of Dijkstra's algoritm in GAMS?
Regards

 Attachments

 dijkstra_web.gms
 (4.71 KiB) Downloaded 77 times
Re: Dijkstra's algorithm
Hello, is there a way to add a constraint so that the shortest path will be picked and all nodes are visited?
Thanks for your help!
Thanks for your help!
Re: Dijkstra's algorithm
rawwi,
No, you cannot easy modify Dijkstra's algorithm to force the shortest path to go through all nodes. This would essentially give you a solution to a traveling salesman problem on the same network, which is a much more difficult problem.
Dirkse
No, you cannot easy modify Dijkstra's algorithm to force the shortest path to go through all nodes. This would essentially give you a solution to a traveling salesman problem on the same network, which is a much more difficult problem.
Dirkse