-
Notifications
You must be signed in to change notification settings - Fork 0
/
Dijkstras.java
128 lines (110 loc) · 4.16 KB
/
Dijkstras.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/*
* Filename : Dijkstras.java
* Problem Statement:
* From a given vertex in a weighted connected graph, find shortest paths to
* other vertices using Dijkstra's algorithm.
* -------------------------------------------------------------------
* AUTHOR : GANESH PAI, Dept. of CS&E, NMAMIT, Nitte
* YEAR : 2021
* E-mail : [email protected]
* ------------------------------------------------------------------------------
*/
import java.util.Arrays;
import java.util.Scanner;
public class Dijkstras {
private class Vertex
{
int distance, parent;
}
private final int INFINITY = 99999;
private int numberOfVertices, sourceNode, graph[][];
private Vertex vertex[];
private void init()
{
graph = new int [numberOfVertices + 1][numberOfVertices + 1];
vertex = new Vertex[numberOfVertices + 1];
for(int i = 1; i <= numberOfVertices; i++)
{
Arrays.fill(graph[i], INFINITY);
graph[i][i] = 0;
vertex[i] = new Vertex();
vertex[i].distance = INFINITY;
}
}
public void readGraph()
{
int v1, v2, edge = 0;
Scanner ip = new Scanner(System.in);
System.out.print("Enter the number of vertices & edges: ");
numberOfVertices = ip.nextInt();
int numberOfEdges = ip.nextInt();
init();
while(edge++ != numberOfEdges)
{
System.out.print("Enter start & end vertex of edge " + edge + ": ");
v1 = ip.nextInt();
v2 = ip.nextInt();
System.out.print("Enter the weight of the edge [" + v1 + "--->" + v2 + "]: ");
graph[v1][v2] = graph[v2][v1] = ip.nextInt();
}
}
public void computeShortestPath(int sourceNode)
{
final int TENTATIVE = 0, PERMANENT = 1;
int nearestNode = sourceNode, currentNode = sourceNode;
int state[] = new int[numberOfVertices + 1];
this.sourceNode = sourceNode;
Arrays.fill(state, TENTATIVE);
state[sourceNode] = PERMANENT;
vertex[sourceNode].distance = 0;
for(int node = 1; node < numberOfVertices; node++)
{
for(int i = 1, min = INFINITY; i <= numberOfVertices; i++) //Node relaxation for all adjacent nodes
{
if( (graph[currentNode][i] != INFINITY) && (state[i] == TENTATIVE) )
{
int newDistance = vertex[currentNode].distance + graph[currentNode][i];
if(newDistance < vertex[i].distance)
{
vertex[i].distance = newDistance;
vertex[i].parent = currentNode;
}
}
if((state[i] == TENTATIVE) && (vertex[i].distance < min))
{
min = vertex[i].distance;
nearestNode = i;
}
}
state[nearestNode] = PERMANENT;
currentNode = nearestNode;
}
}
public void printPaths()
{
for(int targetNode = 1; targetNode <= numberOfVertices; targetNode++)
{
if(sourceNode == targetNode)
continue;
System.out.print(sourceNode + " to " + targetNode + ": ");
pathWalk(targetNode);
System.out.println(":" + vertex[targetNode].distance);
}
}
private void pathWalk(int node)
{
if(node == 0)
return;
pathWalk(vertex[node].parent);
System.out.print(node + " ");
}
public static void main(String[] args) {
Dijkstras dj = new Dijkstras();
dj.readGraph();
System.out.print("\nEnter a source vertex: ");
int sourceVertex = new Scanner(System.in).nextInt();
dj.computeShortestPath(sourceVertex);
System.out.println("\nShortest path from " + sourceVertex + " to all other vertices :");
dj.printPaths();
}
}