-
Notifications
You must be signed in to change notification settings - Fork 0
/
dikstra.txt
41 lines (41 loc) · 1.76 KB
/
dikstra.txt
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
public class Dijkstra {
// Dijkstra's algorithm to find shortest path from one point which can also be taken as a vertex to all other nodes or vertices
public static int [] dijkstra (WeightedGraph G, int s)
{ final int [] dist = new int [G.size()];
// shortest known distance from "s"
final int [] pred = new int [G.size()];
// preceeding node in path
final boolean [] visited = new boolean [G.size()];
// all false initially
for (int i=0; i<dist.length; i++)
{
dist[i] = Integer.MAX_VALUE; }
dist[s] = 0;
for (int i=0; i<dist.length; i++)
{ final int next = minVertex (dist, visited); visited[next] = true;
// The shortest path to next is dist[next] and via pred[next]. final int [] n = G.neighbors (next);
for (int j=0; j<n.length; j++)
{ final int v = n[j]; final int d = dist[next] + G.getWeight(next,v);
if (dist[v] > d) {
dist[v] = d;
pred[v] = next; } } }
return pred;
// (ignore pred[s]==0!) }
private static int minVertex (int [] dist, boolean [] v)
{ int x = Integer.MAX_VALUE; int y = -1; // graph not connected, or no unvisited vertices
for (int i=0; i<dist.length; i++)
{ if (!v[i] && dist[i]<x) {y=i; x=dist[i];} }
return y; }
public static void printPath (WeightedGraph G, int [] pred, int s, int e)
{ final {java.util.ArrayList path = new java.util.ArrayList();
int x = e;
while (x!=s)
{ path.add (0, G.getLabel(x)); x = pred[x]; }
path.add (0, G.getLabel(s));
System.out.println (path); }
}
}
// distances are always positive and dikstra is a positive cycle algorithm.
//the vertices can be taken as the points of the positive graph.
//the weights of the graph can be taken as the distance between the vertices.
// the distances are relaxed with respect to the vertex in question.