Dijkstra’s algorithm in java

ghz 10months ago ⋅ 78 views

Dijkstra's algorithm is used to find the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. Here's a Java implementation of Dijkstra's algorithm using a priority queue:

import java.util.*;

public class DijkstraAlgorithm {

    static class Edge {
        int target;
        int weight;

        public Edge(int target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }

    public static int[] dijkstra(List<List<Edge>> graph, int source) {
        int n = graph.size(); // Number of vertices
        int[] dist = new int[n]; // Array to store shortest distances
        Arrays.fill(dist, Integer.MAX_VALUE); // Initialize distances to infinity
        dist[source] = 0; // Distance from source to source is 0

        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.offer(new Edge(source, 0));

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int u = current.target;

            for (Edge neighbor : graph.get(u)) {
                int v = neighbor.target;
                int weight = neighbor.weight;
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new Edge(v, dist[v]));
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int n = 6; // Number of vertices
        List<List<Edge>> graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // Example graph
        graph.get(0).add(new Edge(1, 2));
        graph.get(0).add(new Edge(2, 4));
        graph.get(1).add(new Edge(2, 1));
        graph.get(1).add(new Edge(3, 7));
        graph.get(2).add(new Edge(4, 3));
        graph.get(3).add(new Edge(5, 1));
        graph.get(4).add(new Edge(3, 2));
        graph.get(4).add(new Edge(5, 5));

        int source = 0; // Source vertex
        int[] distances = dijkstra(graph, source);

        System.out.println("Shortest distances from source vertex " + source + ":");
        for (int i = 0; i < distances.length; i++) {
            System.out.println("Vertex " + i + ": " + distances[i]);
        }
    }
}

In this implementation:

  • We define a static nested class Edge to represent an edge in the graph, containing the target vertex and the weight of the edge.
  • The dijkstra method takes a graph represented as an adjacency list and the source vertex as input and returns an array of shortest distances from the source vertex to all other vertices.
  • We initialize an array dist to store the shortest distances and a priority queue pq to process vertices in the order of increasing distance from the source.
  • We start with the source vertex and iterate through its neighbors, updating the shortest distances to each neighbor if a shorter path is found.
  • The main method creates an example graph, runs Dijkstra's algorithm, and prints the shortest distances from the source vertex to all other vertices.
#algorithm