# Dijkstra Algorithm

a guest
Nov 12th, 2017
1,372
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. package dijkstra;
2.
3. import java.util.Iterator;
4. import java.util.PriorityQueue;
5.
6. public class TestGraphs {
7.
8.     public static void main(String[] args) {
9.         Graph g = new Graph(5);
10.
11.         System.out.println("Graph:");
22.
23.         // print Graph
24.         g.printGraph();
25.
26.         // Dijkstra Shortest Path Algorithm
27.         System.out.println("Dijkstra Shortest Path:");
28.         Dijkstra(g, 0);
29.     }
30.
31.     public static void Dijkstra(Graph g, int startVertex) {
32.         // for storing distances after removing vertex from Queue
33.         float[] distances = new float[g.getvCount()];
34.         // for storing father id's after removing vertex from Queue
35.         int[] parents = new int[g.getvCount()];
36.         for (int i = 0; i < g.getvCount(); i++) {
37.             parents[i] = -1;
38.         }
39.
40.         // set up vertex queue
41.         PriorityQueue<Vertex> Q = new PriorityQueue<Vertex>();
42.         for (int i = 0; i < g.getvCount(); i++) {
43.             if (i != startVertex) {
45.             }
46.         }
47.
49.         Vertex node = new Vertex(startVertex);
50.         node.setDistance(0);
52.
53.         // loop through all vertices
54.         while (!Q.isEmpty()) {
55.             // get vertex with shortest distance
56.             Vertex u = Q.remove();
57.             distances[u.getId()] = u.getDistance();
58.
59.             // iterate through all neighbours
60.             Iterator<Edge> it = g.neighbours(u.getId()).iterator();
61.             while (it.hasNext()) {
62.                 Edge e = it.next();
63.                 Iterator<Vertex> it2 = Q.iterator();
64.                 while (it2.hasNext()) {
65.                     Vertex v = it2.next();
66.                     // check if vertex was visited already
67.                     if (e.getEndPoint() != v.getId()) {
68.                         continue;
69.                     }
70.                     // check distance
71.                     if (v.getDistance() > u.getDistance() + e.getWeight()) {
72.                         v.setDistance(u.getDistance() + e.getWeight());
73.                         v.setParent(u);
74.                         parents[v.getId()] = v.getParent().getId();
75.                     }
76.                 }
77.             }
78.
79.         }
80.
81.         // print final shortest paths
82.         System.out.println("Vertex\tDistance\tParent Vertex");
83.         for (int i = 0; i < g.getvCount(); i++) {
84.             System.out.println(i + "\t" + distances[i] + "\t\t" + parents[i]);
85.         }
86.
87.     }
88. }