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**:

**Implementation – **Adjacency List and Priority Queue

**Prerequisites**: Dijkstra Algorithm and Pair Class

**Complete Algorithm**:

- Will create pair object for each vertex with two information’s, vertex and distance. (similar to heap node)
- Override the Comparator for TreeSet sort them based on the key
- Use SPT[] to keep track of the vertices which are currently in Shortest Path Tree(SPT).
- 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).
- Create a pair object for vertex 0 with distance 0 and insert into priority queue.
- while tree set is not empty
- Extract the min node from the tree set, say it vertex
*u* and add it to the SPT.
- 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

**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..-**

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

__________________________________________________

### Like this:

Like Loading...