Dijkstra Algorithm Implementation – TreeSet and Pair Class

Earlier we have seen what Dijkstra algorithm is is and how it works. In this article we will see its implementation using adjacency list and TreeSet.

Example:

Dijkstra - Shortest Path Algorithm

Implementation – Adjacency List and Priority Queue

Prerequisites: Dijkstra Algorithm and Pair Class

Complete Algorithm:

  1. Will create pair object for each vertex with two information’s, vertex and distance. (similar to heap node)
  2. Override the Comparator for TreeSet sort them based on the key
  3. Use SPT[] to keep track of the vertices which are currently in Shortest Path Tree(SPT).
  4. Create distance [] to keep track of distance for each vertex from the source. , initialize all distances as MAX_VAL except the first vertex for which distance will 0. (Start from first vertex).
  5. Create a pair object for vertex 0 with distance 0 and insert into priority queue.
  6. while tree set is not empty
    1. Extract the min node from the tree set, say it vertex u and add it to the SPT.
    2. For adjacent vertex v, if v is not in SPT[] and distance[v] > distance[u] + edge u-v weight then update distance[v] = distance[u] + edge u-v weight  and add it to the tree set.

Total vertices: V, Total Edges : E

  • O(logV) – to extract each vertex from queue. So for V vertices – O(VlogV)
  • O(logV) – each time new pair object with new key value of a vertex and will be done for at most once for each edge. So for total E edge – O(ElogV)
  • So over all complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)

See the animation below for more understanding

1-32
previous arrow
next arrow
PlayPause
Slider

Complete Code:

Output:

Dijkstra Algorithm: (Adjacency List + TreeSet)

Source Vertex: 0 to vertex 0 distance: 0
Source Vertex: 0 to vertex 1 distance: 4
Source Vertex: 0 to vertex 2 distance: 3
Source Vertex: 0 to vertex 3 distance: 6
Source Vertex: 0 to vertex 4 distance: 8
Source Vertex: 0 to vertex 5 distance: 14

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: