Dijkstra’s-–-Shortest-Path-Algorithm-SPT-–-Adjacency-Matrix-–-Java-Implementation

Posted on | Views:

Link

Dijkstra’s – Shortest Path Algorithm (SPT) – Adjacency Matrix

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
public class DijkstraAdjacencyMatrix {

    static class Graph {
        int vertices;
        int matrix[][];

        public Graph(int vertex) {
            this.vertices = vertex;
            matrix = new int[vertex][vertex];
        }

        public void addEdge(int source, int destination, int weight) {
            // add edge
            matrix[source][destination] = weight;
            // add back edge for undirected graph
            matrix[destination][source] = weight;
        }

        // get the vertex with minimum distance which is not included in SPT
        int getMinimumVertex(boolean[] mst, int[] distance) {
            int minDistance = Integer.MAX_VALUE;
            int vertex = -1;
            for (int i = 0; i < vertices; i++) {
                if (mst[i] == false && distance[i] < minDistance) {
                    minDistance = distance[i];
                    vertex = i;
                }
            }
            return vertex;
        }

        public void dijkstra_GetMinDistances(int sourceVertex) {
            boolean[] spt = new boolean[vertices];
            int[] distance = new int[vertices];
            int INFINITY = Integer.MAX_VALUE;

            // Initialize all the distance to infinity
            for (int i = 0; i < vertices; i++) {
                distance[i] = INFINITY;
            }

            // start from the vertex 0
            distance[sourceVertex] = 0;

            // create SPT
            for (int i = 0; i < vertices; i++) {
                // get the vertex with the minimum distance
                int vertex_U = getMinimumVertex(spt, distance);
                // include this vertex in SPT
                spt[vertex_U] = true;
                // iterate through all the adjacent vertices of above vertex and update the keys
                for (int vertex_V = 0; vertex_V < vertices; vertex_V++) {
                    // check of the edge between vertex_U and vertex_V
                    if (matrix[vertex_U][vertex_V] > 0) {
                        // check if this vertex 'vertex_V' already in spt and
                        // if distance[vertex_V]!=Infinity
                        if (spt[vertex_V] == false) {
                            // check if distance needs an update or not
                            // means check total weight from source to vertex_V is less than
                            // the current distance value, if yes then update the distance
                            int distanceToV = distance[vertex_U] + matrix[vertex_U][vertex_V];
                            if (distanceToV < distance[vertex_V])
                                distance[vertex_V] = distanceToV;
                        }
                    }
                }
            }
            // print shortest path tree
            printDijkstra(sourceVertex, distance);
        }

        public void printDijkstra(int sourceVertex, int[] distance) {
            System.out.println("Dijkstra Algorithm: (Adjacency Matrix)");
            for (int i = 0; i < vertices; i++) {
                System.out.println("Source Vertex: " + sourceVertex + " to vertex " + +i + " distance: " + distance[i]);
            }
        }
    }

    public static void main(String[] args) {
        int vertices = 6;
        Graph graph = new Graph(vertices);
        int sourceVertex = 0;
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 2, 3);
        graph.addEdge(1, 2, 1);
        graph.addEdge(1, 3, 2);
        graph.addEdge(2, 3, 4);
        graph.addEdge(3, 4, 2);
        graph.addEdge(4, 5, 6);
        graph.dijkstra_GetMinDistances(sourceVertex);
    }
}

0%