Skip to content

Latest commit

 

History

History
74 lines (50 loc) · 3.68 KB

dijkstra.md

File metadata and controls

74 lines (50 loc) · 3.68 KB
Raw

Dijkstra's Algorithm

Whenever you come across a scenario where you have to find the shortest distance to a set of points in a weighted graph from a given starting point,the best possible approach that can be used is Dijkstra's Algorithm

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.

Approach

In breadth first search(bfs),when the graph is unweighted one can notice the fact that the vertices that are printed before a given vertices will always have a shorter or equal(in case of being neighbours) path length from the root node.What dijkstra does is, it deploys a similar method with tweaks such that now even weights can be considered.

There are certain steps that dijkstra's algorithm follows till it covers all the vertices,which can be abstracted in the following manner:

  • Every time that we set out to visit a new node, we will choose the node with the smallest known distance/cost to visit first.
  • Once we’ve moved to the node we’re going to visit, we will check each of its neighboring nodes.
  • For each neighboring node, we’ll calculate the distance/cost for the neighboring nodes by summing the cost of the edges that lead to the node we’re checking from the starting vertex.
  • Finally, if the distance/cost to a node is less than a known distance, we’ll update the shortest distance that we have on file for that vertex.

These instructions are our golden rules that we will always follow, until our algorithm is done running. So, let’s get to it!

Pseudo Code

function Dijkstra(Graph, source):
       dist[source]  := 0                     // Distance from source to source is set to 0
       for each vertex v in Graph:            // Initializations
           if v ≠ source
               dist[v]  := infinity           // Unknown distance function from source to each node set to infinity
           add v to Q                         // All nodes initially in Q

      while Q is not empty:                  // The main loop
          v := vertex in Q with min dist[v]  // In the first run-through, this vertex is the source node
          remove v from Q 

          for each neighbor u of v:           // where neighbor u has not yet been removed from Q.
              alt := dist[v] + length(v, u)
              if alt < dist[u]:               // A shorter path to u has been found
                  dist[u]  := alt            // Update distance of u 

      return dist[]
  end function

Example

The following illustrations gives an insight to Djikstra's algorithm implementation.

  • Initialize distances according to the algorithm.

  • Pick first node and calculate distances to adjacent nodes.

  • Pick next node with minimal distance; repeat adjacent node distance calculations.

  • Final result of shortest-path tree