Menu
I would like to see an example of a Dijkastra search algorithm for a graph built using Ruby's RGL (http://rgl.rubyforge.org/) or GRATR (http://rubyforge.org/projects/gratr/).
I know GRATR has Dijkastra support but I'm not really sure how to go about using it, any help would be appreciated.
995
Dijkstra's Algorithm can only work with graphs that have positive weights. This is because, during the process, the weights of the edges have to be added to find the shortest path. If there is a negative weight in the graph, then the algorithm will not work properly.
The total weight of a path in a weighted graph is the sum of the weights of all the edges on the path. A path between two nodes that has minimum total weight is called a shortest path.
Dijkstra's algorithm, published in 1959 and named after its creator Dutch computer scientist Edsger Dijkstra, can be applied on a weighted graph. The graph can either be directed or undirected. One stipulation to using the algorithm is that the graph needs to have a nonnegative weight on every edge.
One of these should help:
http://snippets.dzone.com/posts/show/7331
http://snippets.dzone.com/posts/show/6100
http://github.com/dbrady/dijkstra
This is an example of dijkstra in GRATR
http://gratr.rubyforge.org/svn/examples/graph_self.rb
185
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
