Dijkstra Algorithm

  • Dijkstra’s algorithm, given by a Dutch scientist Edsger Dijkstra in 1959, is used to find the shortest path tree. This algorithm is widely used in network routing protocols, most notably IS-IS and OSPF (Open Shortest Path First).
  • Djikstra's algorithm solves the problem of finding the shortest path from a point in a graph (the source) to a destination. It turns out that one can find the shortest paths from a given source to all points in a graph in the same time, hence this problem is sometimes called the singlesource shortest paths problem.
  • The somewhat unexpected result that all the paths can be found as easily as one further demonstrates the value of reading the literature on algorithms!
  • This problem is related to the spanning tree one. The graph representing all the paths from one vertex to all the others must be a spanning tree - it must include all vertices.
  • There will also be no cycles as a cycle would define more than one path from the selected vertex to at least one other vertex.

Algorithm

Step 1: Select the source node also called the initial node 
Step 2: Define an empty set N that will be used to hold nodes to which a shortest path has been found. 
Step 3: Label the initial node with , and insert it into N. 
Step 4: Repeat Steps 5 to 7 until the destination node is inNor there are no more labelled nodes in N. 
Step 5: Consider each node that is not in N and is connected by an edge from the newly inserted node. 
Step 6: (a) If the node that is not in N has no label then SET the label of the node = the label of the newly inserted node + the length of the edge.
        (b) Else if the node that is not in N was already labelled, then SET its new label = minimum (label of newly inserted vertex + length of edge, old label) 
Step 7: Pick a node not in N that has the smallest label assigned to it and add it to N.

Explanation

  • Dijkstra’s algorithm labels every node in the graph where the labels represent the distance (cost) from the source node to that node.
  • There are two kinds of labels: temporary and permanent. Temporary labels are assigned to nodes that have not been reached, while permanent labels are given to nodes that have been reached and their distance (cost) to the source node is known.
  • A node must be a permanent label or a temporary label, but not both.