8a. DIJKSTRAS ALGORITHM
AIM:
To write a java program
to implement Dijkstra Algorithm.
ALGORITHM:
1.Initialization
of all nodes with distance "infinite"; initialization of the starting
node with 0
2.Marking of the
distance of the starting node as permanent, all other distances as temporarily.
3.Setting of
starting node as active.
4.Calculation of
the temporary distances of all neighbour nodes of the active node by summing up
its distance with the weights of the edges.
5.If such a calculated
distance of a node is smaller as the current one, update the distance and set
the current node as antecessor. This step is also called update and is
Dijkstra's central idea.
6.Setting of the
node with the minimal temporary distance as active. Mark its distance as
permanent.
Repeating of steps 4 to 7 until there aren't any nodes left with a
permanent distance, which neighbours still have temporary distance
PROGRAM:
import
java.util.HashSet;
import
java.util.InputMismatchException;
import java.util.Iterator;
import
java.util.Scanner;
import
java.util.Set;
public class
DijkstraAlgorithmSet
{
private int
distances[];
private
Set<Integer> settled;
private
Set<Integer> unsettled;
private int
number_of_nodes;
private int
adjacencyMatrix[][];
public DijkstraAlgorithmSet(int
number_of_nodes)
{
this.number_of_nodes
= number_of_nodes;
distances = new
int[number_of_nodes + 1];
settled = new
HashSet<Integer>();
unsettled = new
HashSet<Integer>();
adjacencyMatrix =
new int[number_of_nodes + 1][number_of_nodes + 1];
}
public void
dijkstra_algorithm(int adjacency_matrix[][], int source)
{
int evaluationNode;
for (int i = 1; i
<= number_of_nodes; i++)
for (int j = 1; j
<= number_of_nodes; j++)
adjacencyMatrix[i][j]
= adjacency_matrix[i][j];
for (int i = 1; i
<= number_of_nodes; i++)
{
distances[i] =
Integer.MAX_VALUE;
}
unsettled.add(source);
distances[source] =
0;
while
(!unsettled.isEmpty())
{
evaluationNode =
getNodeWithMinimumDistanceFromUnsettled();
unsettled.remove(evaluationNode);
settled.add(evaluationNode);
evaluateNeighbours(evaluationNode);
}
}
private int
getNodeWithMinimumDistanceFromUnsettled()
{
int min ;
int node = 0;
Iterator<Integer>
iterator = unsettled.iterator();
node =
iterator.next();
min =
distances[node];
for (int i = 1; i
<= distances.length; i++)
{
if
(unsettled.contains(i))
{
if (distances[i]
<= min)
{
min = distances[i];
node = i;
}
}
}
return node;
}
private void
evaluateNeighbours(int evaluationNode)
{
int edgeDistance =
-1;
int newDistance =
-1;
for (int
destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++)
{
if
(!settled.contains(destinationNode))
{
if
(adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE)
{
edgeDistance =
adjacencyMatrix[evaluationNode][destinationNode];
newDistance =
distances[evaluationNode] + edgeDistance;
if (newDistance <
distances[destinationNode])
{
distances[destinationNode]
= newDistance;
}
unsettled.add(destinationNode);
}
}
}
}
public static void
main(String... arg)
{
int
adjacency_matrix[][];
int
number_of_vertices;
int source = 0;
Scanner scan = new
Scanner(System.in);
try
{
System.out.println("Enter
the number of vertices");
number_of_vertices =
scan.nextInt();
adjacency_matrix =
new int[number_of_vertices + 1][number_of_vertices + 1];
System.out.println("Enter
the Weighted Matrix for the graph");
for (int i = 1; i
<= number_of_vertices; i++)
{
for (int j = 1; j
<= number_of_vertices; j++)
{
adjacency_matrix[i][j]
= scan.nextInt();
if (i == j)
{
adjacency_matrix[i][j]
= 0;
continue;
}
if
(adjacency_matrix[i][j] == 0)
{
adjacency_matrix[i][j]
= Integer.MAX_VALUE;
}
}
}
System.out.println("Enter
the source ");
source =
scan.nextInt();
DijkstraAlgorithmSet
dijkstrasAlgorithm = new DijkstraAlgorithmSet(number_of_vertices);
dijkstrasAlgorithm.dijkstra_algorithm(adjacency_matrix,
source);
System.out.println("The
Shorted Path to all nodes are ");
for (int i = 1; i
<= dijkstrasAlgorithm.distances.length - 1; i++)
{
System.out.println(source
+ " to " + i + " is "+ dijkstrasAlgorithm.distances[i]);
}
} catch
(InputMismatchException inputMismatch)
{
System.out.println("Wrong
Input Format");
}
scan.close();
}
}