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

Video

Wiki

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