Dijkstra's algorithm

Archive of Gamsworld Google Group
Post Reply
Archiver
User
User
Posts: 7876
Joined: 2 years ago

Dijkstra's algorithm

Post by Archiver » 8 years ago


Hi

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

Regards



Archiver
User
User
Posts: 7876
Joined: 2 years ago

RE: Dijkstra's algorithm

Post by Archiver » 8 years ago


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: 2 years ago

Re: Dijkstra's algorithm

Post by Archiver » 8 years ago


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: 2 years ago

Re: Dijkstra's algorithm

Post by Archiver » 8 years ago


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: 2 years ago

Re: Dijkstra's algorithm

Post by Archiver » 8 years ago


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: 2 years ago

RE: Dijkstra's algorithm

Post by Archiver » 8 years ago


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: 2 years ago

Re: Dijkstra's algorithm

Post by Archiver » 8 years ago


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: 2 years ago

Re: Dijkstra's algorithm

Post by Archiver » 6 years ago

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 73 times

rawwi
User
User
Posts: 1
Joined: 1 month ago

Re: Dijkstra's algorithm

Post by rawwi » 1 month ago

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: 75
Joined: 3 years ago
Location: Fairfax, VA

Re: Dijkstra's algorithm

Post by dirkse » 1 month ago

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