forked from ronijpandey/Java-Codes
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDijkstra.java
More file actions
118 lines (79 loc) · 3.27 KB
/
Dijkstra.java
File metadata and controls
118 lines (79 loc) · 3.27 KB
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
package javacodes;
import java.util.*;
//this program uses dijsktra's algorithm to find single source shortest path.
//it also uses adjacency matrix for graph representation.
public class Dijkstra {
static int V;
//function to find vertex with the shortest path.
int minDistance(int dist[], Boolean que[])
{
int min = Integer.MAX_VALUE, index=-1;
for (int i = 0; i < V; i++)
if (que[i] == false && dist[i] <= min)
{
min = dist[i];
index = i;
}
return index;
}
//function to print all the node with there minimum distance from the source
void printSolution(int dist[], int n)
{
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i+" \t\t "+dist[i]);
}
//function to implement dijkstra algorithm
void dijkstra(int graph[][], int src)
{
//shortest distance for each node from the source node(src)
int dist[] = new int[V];
//all the nodes with minimun distance from the source
Boolean que[] = new Boolean[V];
// Give infinite value to all nodes
for (int i = 0; i < V; i++)
{
dist[i] = Integer.MAX_VALUE;
que[i] = false;
}
//distance of source node is always 0
dist[src] = 0;
for (int count = 0; count < V-1; count++)
{
//find minimum distance node from the source
//u=src in the first iteration
int u = minDistance(dist, que);
//mark u to have found the shortest distance from the source
que[u] = true;
for (int i = 0; i < V; i++)
/*update the value of i if and only if
* the node i is not added in the MST
* and there exists a path from u to v
* and the distance of u from the source node is not Infinite
* and distance of i from the source node is less than
* the distance of u and current value of i from u
*/
if (!que[i] && graph[u][i]!=0 &&
dist[u] != Integer.MAX_VALUE &&
dist[u]+graph[u][i] < dist[i])
dist[i] = dist[u] + graph[u][i];
}
//print the minimum distance for each node from the source
printSolution(dist, V);
}
public static void main (String[] args)
{
Scanner in=new Scanner(System.in);
System.out.println("Number of vertices:");
V=in.nextInt();
int [][]graph = new int[V][V];
System.out.println("Rows and Column of matrix:");
for(int i=0;i<V;i++)
{
for(int j=0;j<V;j++)
graph[i][j]=in.nextInt();
}
Dijkstra ob=new Dijkstra();
ob.dijkstra(graph, 0);
}
}