Dijkstra’s algorithm

This algorithm finds shortest path from a graph structures which has 2 elements known as,

  1. Nodes/Vertices
  2. Edges


A node (or vertex) is a discrete position in the graph.And an edge (or connection) is a link between two vertices that can be either directed or undirected and may have a cost associated with it.

The 2 vertices connected by edge are source and destination.The length of edge denotes distance/cost between 2 nodes.

Code Implementation:

class Edge

 attr_accessor :src, :dst, :length

 def initialize(src, dst, length = 1)

   @src = src

   @dst = dst

   @length = length




Graph is an array of such edges.It may contain loops.

It can be initialized as,

def initialize

@edges = []


Connecting 2 vertices by creating a edge between them with certain length,

def connect(src, dst, length = 1)

   unless self.include?(src)

     raise ArgumentException, “No such vertex: #{src}”


   unless self.include?(dst)

     raise ArgumentException, “No such vertex: #{dst}”


   @edges.push Edge.new(src, dst, length)


 Rules of Dijkstra’s game

  1. From the starting node, visit the vertex with the smallest known distance.
  2. Once we’ve moved to the smallest-cost vertex,check each of its neighbouring nodes.
  3. Calculate the distance/cost from the neighbouring nodes by summing the cost of edges leading from the start vertex.
  4. If the distance to a vertex we are checking is less than a known distance, update the shortest distance for that vertex.

Consider below ex:

Step 1:Initialize the distance as infinite from start node.

Visited =[] unvisited=[a,b,c,d,e]

Step2: Visit each nodes.

The distance to node b is currently marked as 7 . But, there is a shorter path to b, which goes through c, and has a cost of only 4. So, the table will be updated with shorter paths.

After visiting all nodes, the table becomes


So we have visited all nodes. The shortest path for all nodes from any node can be found from above table.


Code implementation:


def dijkstra(src, dst = nil)

   distances = {}

   previouses = {}

   self.each do |vertex|

     distances[vertex] = nil # Infinity

     previouses[vertex] = nil


   distances[src] = 0

   vertices = self.clone

   until vertices.empty?

     nearest_vertex = vertices.inject do |a, b|

       next b unless distances[a]

       next a unless distances[b]

       next a if distances[a] < distances[b]



     break unless distances[nearest_vertex] # Infinity

     if dst and nearest_vertex == dst

       return distances[dst]


     neighbors = vertices.neighbors(nearest_vertex)

     neighbors.each do |vertex|

       alt = distances[nearest_vertex] + vertices.length_between(nearest_vertex, vertex)

       if distances[vertex].nil? or alt < distances[vertex]

         distances[vertex] = alt

         previouses[vertices] = nearest_vertex

         # decrease-key v in Q # ???



     vertices.delete nearest_vertex


   if dst

     return nil


     return distances




#Creating graph

graph = Graph.new

(1..6).each {|node| graph.push node }


#Connecting 2 nodes

graph.connect 1, 2, 7

#connect all nodes like above

#Find cost/distance

graph.length_between(2, 1)

#Find shortest path

graph.dijkstra(1, 5)

Leave a Reply

Your email address will not be published.