# Djkstra’s – Shortest Path Algorithm (SPT)

**What is Dijkstra’s algorithm?**

- Dijkstra algorithm is a greedy algorithm.
- It finds a shortest path tree for a weighted undirected graph.
- This means it finds a shortest paths between nodes in a graph, which may represent, for example, road networks
- For a given source node in the graph, the algorithm finds the shortest path between source node and every other node.
- This algorithm also used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined.
- Dijkstra’s algorithm is very similar to Prim’s algorithm. In Prim’s algorithm we create minimum spanning tree (MST) and in Dijkstra algorithm we create
*shortest path tree (SPT)*from the given source..

**Example**:

**How to implement Dijkstra’s algorithm?**

- Start with the empty Shortest Path Tree (SPT).
- Maintain a set SPT[] to keep track to vertices included in SPT.
- Assign a distance value to all the vertices, (say distance []) and initialize all the distances with +∞ (Infinity) except the source vertex. This will be used to keep track of distance of vertices from the source vertex. Distance of source vertex to source vertex will be 0.
- Repeat the following steps until all vertices are processed.
- Pick the vertex
which is not in*u*and has minimum distance.*SPT[]* - Add vertex
to*u**SPT[].* - Loop over all the adjacent vertices of
- For adjacent vertex v, if v is not in SPT[] and distance[v] > distance[u] + edge u-v
then update*weight**distance[v] = distance[u] + edge u-v weight*

- Pick the vertex

Please see the animation below for better understanding.

**Ways to Implement:**

- Adjacency Matrix – Searching.
- Adjacency List – Binary Heap
- Adjacency List – Priority Queue
- Adjacency List – TreeMap and Pair class

**Time Complexity:**

The time complexity of Dijkstra algorithm depends on the data structures used for the graph and for ordering the edges by weight.

Data Structure of Graph | Ordering | Time Complexity |

Adjacency Matrix | Searching | O(|V|^{2}) |

Adjacency List | Binary Heap | O(|E|log|V|) |

Adjacency List | Priority Queue | O(|E|log|V|) |

Adjacency List | TreeMap | O(|E|log|V|) |

**Usages**:

- Dijkstra’s algorithm can be used to find the shortest route between one city and all other cities.
- Shortest path algorithm is used in network routing protocols,
- IS-IS (Intermediate System to Intermediate System)
- Open Shortest Path First (OSPF).

Reference – Wiki