# Implement Dijkstra

### Implement Dijkstra

##### Given an adjacency matrix (graph), find the shortest distance of all the vertex’s from the source vertex.

It is very similar to {@link PrimMinimumSpanningTree}, in prim we just take edge weight but here we take summation for edge’s weight from source.

##### Algorithm:
• Let the distance of start vertex from start vertex = 0
• Let the distance for all other vertex from start vertex = INFINITY
• Repeat
• Visit the unvisited vertex with the smallest known distance from the start vertex
• For the current vertex, examine its unvisited neighbours
• For the current vertex, calculate distance of each neighbours from start vertex
• If the calculated distance of a vertex is less than known distance, update the shortest distance
• Update the previous vertex for each of the updated distances
• Add the current vertex to the list of the visited vertices

Latest Source Code:
Github: DijkstraShortestPath.java

Output:

``` Vertex	Distance	Parent
0		0			-1
1		4			0
2		12			1
3		19			2
4		21			5
5		11			6
6		9			7
7		8			0
8		14			2
```
Author: