Page 1 of 2

Dijkstra's algorithm

Posted: Mon Dec 13, 2010 3:38 pm
by Archiver

Hi

Do you know any implementation's of Dijkstra's algoritm in GAMS?

Regards



RE: Dijkstra's algorithm

Posted: Mon Dec 13, 2010 3:44 pm
by Archiver

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

Posted: Mon Dec 13, 2010 4:58 pm
by Archiver

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

Posted: Tue Dec 14, 2010 10:04 am
by Archiver

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

Posted: Tue Dec 14, 2010 10:15 am
by Archiver

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

Posted: Wed Dec 15, 2010 9:58 am
by Archiver

Dear Renger
Thank you for this.
Do you have any idea of the performance of this algorythm when applied to large-scale 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 e-mail, any attachments and the information it contains are confidential and meant only for the use of the addressee(s) only. Access to this e-mail 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 e-mail in error, please notify us immediately by e-mail or telephone and delete the e-mail from any computer.
All reasonable precautions have been taken to ensure no viruses are present in this e-mail and its attachments. As our company cannot accept responsibility for any loss or damage arising from the use of this e-mail 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

Posted: Wed Dec 15, 2010 4:28 pm
by Archiver

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

Posted: Mon Jul 15, 2013 7:35 pm
by Archiver
Reply-to: 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 t-matrix, and added the origin-destination pair (3,4). The shortest path I got according to this code is 3-5-4, total length 2.774. But there is another path, 3-8-7-5-4, 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

--

Re: Dijkstra's algorithm

Posted: Fri Aug 02, 2019 4:38 pm
by rawwi
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!

Re: Dijkstra's algorithm

Posted: Mon Aug 05, 2019 6:43 pm
by dirkse
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