# 1. Introduction

Dijkstra’s Algorithm is a classic graph algorithm that is used to find the shortest path from a starting node to all other nodes in a weighted graph. The algorithm works on both directed and undirected graphs. However, it does not account for negative weights. In this blog post, we’ll delve into its implementation in Java.

# 2. Program Steps

1. Represent the graph using an adjacency matrix.

2. Initialize a *distance* array with *Integer.MAX_VALUE* (considered as infinity) for all nodes except the starting node which will have a distance of 0.

3. Use a *boolean* array *sptSet* (shortest path tree set) to keep track of vertices for which the shortest distance is finalized.

4. For each vertex not yet included in *sptSet*, choose a vertex with the minimum distance value.

5. Update the distance value of the adjacent vertices of the chosen vertex.

6. Repeat the process for all the vertices.

# 3. Code Program

```
class DijkstraAlgorithm {
private static final int V = 5; // Number of vertices in the graph
// Utility function to find the vertex with minimum distance
private int minDistance(int[] dist, boolean[] sptSet) {
int min = Integer.MAX_VALUE, minIndex = -1;
for (int v = 0; v < V; v++) {
if (!sptSet[v] && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}
public void dijkstra(int[][] graph, int src) {
int[] dist = new int[V]; // Output array. dist[i] holds shortest distance from src to i
boolean[] sptSet = new boolean[V];
for (int i = 0; i < V; i++) {
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++) {
if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
printSolution(dist);
}
private void printSolution(int[] dist) {
System.out.println("Vertex \t\t Distance from Source");
for (int i = 0; i < V; i++) {
System.out.println(i + " \t\t " + dist[i]);
}
}
}
public class Main {
public static void main(String[] args) {
int[][] graph = new int[][]{
{0, 4, 0, 0, 0},
{4, 0, 8, 0, 0},
{0, 8, 0, 7, 0},
{0, 0, 7, 0, 9},
{0, 0, 0, 9, 0}
};
DijkstraAlgorithm dijkstra = new DijkstraAlgorithm();
dijkstra.dijkstra(graph, 0);
}
}
```

### Output:

Vertex Distance from Source 0 0 1 4 2 12 3 19 4 28

# 4. Step By Step Explanation

1. The given graph is represented using an adjacency matrix. A value of *0* indicates no direct edge between the vertices.

2. The *minDistance* method finds the vertex with the minimum distance from the source, among the set of vertices not yet included in the shortest path tree.

3. The *dijkstra* method calculates the shortest path from a source vertex to every other vertex. It iteratively finalizes the shortest distance for every vertex.

4. During each iteration, it picks a vertex which is not in the *sptSet* and has a minimum distance from the source.

5. For every adjacent vertex *v*, if the sum of the current distance value of *u* and the weight of edge *u-v*, is less than the distance value of *v*, then update the distance value of *v*.

6. The *printSolution* method outputs the shortest distance of each vertex from the source vertex.

7. The *Main* class creates a sample graph and initiates the Dijkstra's algorithm on it. The output represents the shortest path from vertex 0 to every other vertex in the graph.