Dijkstra's algorithm

Archive of Gamsworld Google Group
Archiver
User
User
Posts: 7876
Joined: 7 years ago

Dijkstra's algorithm

Post by Archiver »


Hi

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

Regards


Archiver
User
User
Posts: 7876
Joined: 7 years ago

RE: Dijkstra's algorithm

Post 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.
Archiver
User
User
Posts: 7876
Joined: 7 years ago

Re: Dijkstra's algorithm

Post 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

Archiver
User
User
Posts: 7876
Joined: 7 years ago

Re: Dijkstra's algorithm

Post 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.
Archiver
User
User
Posts: 7876
Joined: 7 years ago

Re: Dijkstra's algorithm

Post 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


Archiver
User
User
Posts: 7876
Joined: 7 years ago

RE: Dijkstra's algorithm

Post 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.
Archiver
User
User
Posts: 7876
Joined: 7 years ago

Re: Dijkstra's algorithm

Post 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.
Archiver
User
User
Posts: 7876
Joined: 7 years ago

Re: Dijkstra's algorithm

Post 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

--
Attachments
dijkstra_web.gms
(4.71 KiB) Downloaded 488 times
rawwi
User
User
Posts: 1
Joined: 4 years ago

Re: Dijkstra's algorithm

Post 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!
User avatar
dirkse
Moderator
Moderator
Posts: 214
Joined: 7 years ago
Location: Fairfax, VA

Re: Dijkstra's algorithm

Post 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
Post Reply