Dijkstra’s algorithm implementation in java

 Dijkstra’s algorithm : It is a algorithm to find the shortest path between nodes in a graph. It deals with ‘graph’ data structure. It suits for both directed and undirected graph.

Usage:

GPS navigation, Pathfinding in AI and routing.

Logic:

• Assign the starting node with distance 0 and remaining node as infinity.
• Visit the nearest node(unvisited),find the shortest distance and mark it as visited.
• Now, add the distance value.
• In the same way, find the shortest route by visiting all nodes.
• Finally, print the value.

Program:

import java.util.*;

class Graph {

    private int g_vertices;

    private List<List<Node>> l_adjList;

    static class Node implements Comparable<Node> {

        int g_vertex;

        int s_distance;

        Node(int g_vertex, int s_distance) {

            this.g_vertex = g_vertex;

            this.s_distance = s_distance;

        }

        @Override

        public int compareTo(Node other) {

            return Integer.compare(this.s_distance, other.s_distance);

        }

    }

    Graph(int g_vertices) {

        this.g_vertices = g_vertices;

        l_adjList = new ArrayList<>();

        for (int i = 0; i < g_vertices; i++) {

            l_adjList.add(new ArrayList<>());

        }

    }

    //Code for undirected graph

    void addEdge(int src, int dest, int weight) {

        l_adjList.get(src).add(new Node(dest, weight));

        l_adjList.get(dest).add(new Node(src, weight));

    }

    void dijkstra(int src) {

        PriorityQueue<Node> pq1 = new PriorityQueue<>();

        int[] distances = new int[g_vertices];

        Arrays.fill(distances, Integer.MAX_VALUE);

        distances[src] = 0;

        pq1.add(new Node(src, 0));

        while (!pq1.isEmpty()) {

            Node current = pq1.poll();

            int u = current.g_vertex;

            for (Node neighbor : l_adjList.get(u)) {

                int v = neighbor.g_vertex;

                int weight = neighbor.s_distance;

                if (distances[u] + weight < distances[v]) {

                    distances[v] = distances[u] + weight;

                    pq1.add(new Node(v, distances[v]));

                }

            }

        }

        System.out.println("Vertex \tSource Distance");

        for (int i = 0; i < g_vertices; i++) {

            System.out.println(i + "\t" + distances[i]);

        }

    }

}

public class DijkstraAlgorithmEg {

    public static void main(String[] args) {

        Graph g1 = new Graph(6);

        g1.addEdge(0, 1, 5);

        g1.addEdge(0, 2, 3);

        g1.addEdge(1, 3, 4);

        g1.addEdge(1, 4, 10);

        g1.addEdge(2, 5, 7);

        g1.addEdge(4, 3, 4);

        g1.addEdge(3, 5, 11);

        g1.dijkstra(0);

    }

}

Output:

C:\raji\blog>javac DijkstraAlgorithmEg.java

C:\raji\blog>java DijkstraAlgorithmEg

Vertex  Source Distance

0       0

1       5

2       3

3       9

4       13

5       10

Here, the implementation of Dijkstra algorithm in java was successful. Hope, this code is useful to you. Keep coding!!!