java coding test course, Dijkstra

In this post, we will learn about Dijkstra’s algorithm and solve a problem using it. Dijkstra’s algorithm is an algorithm used to find the shortest path between each vertex in a graph and is mainly used in various pathfinding problems.

1. Understanding the Algorithm

Dijkstra’s algorithm is an efficient method for finding the shortest path from a starting vertex to all other vertices in a weighted graph. This algorithm works by calculating the path length to reach specific vertices and continuously updating the shortest path.

1.1. Basic Concepts

• Weighted Graph: A graph where each edge has a cost or weight assigned to it.
• Priority Queue: Used to manage the current shortest paths.
• Greedy Approach: A method of finding shorter paths based on the currently discovered shortest path.

2. Problem Statement

Problem Description

This problem involves finding the shortest path between the starting vertex and the destination vertex in a given weighted graph. The graph is provided with a number of vertices and edges, and the weights of each edge are also given.

Input

• First line: Number of vertices N (1 ≤ N ≤ 1000)
• Second line: Number of edges M (1 ≤ M ≤ 10000)
• Third line: Starting vertex S, destination vertex E
• The next M lines: Starting vertex A, ending vertex B, weight W of each edge (1 ≤ A, B ≤ N, 1 ≤ W ≤ 10000)

Output

Print the length of the shortest path from the starting vertex S to the destination vertex E. If it cannot be reached, print -1.

3. Writing the Code

3.1. Java Code

import java.util.*;

public class Dijkstra {
    static class Edge {
        int to;
        int weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Graph construction
        int N = scanner.nextInt(); // Number of vertices
        int M = scanner.nextInt(); // Number of edges
        int S = scanner.nextInt(); // Starting vertex
        int E = scanner.nextInt(); // Destination vertex

        List[] graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        // Receive edge input
        for (int i = 0; i < M; i++) {
            int A = scanner.nextInt();
            int B = scanner.nextInt();
            int W = scanner.nextInt();
            graph[A].add(new Edge(B, W));
            graph[B].add(new Edge(A, W)); // Undirected graph
        }

        // Execute Dijkstra's algorithm
        int result = dijkstra(graph, N, S, E);
        System.out.println(result);
    }

    public static int dijkstra(List[] graph, int N, int start, int end) {
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

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

        boolean[] visited = new boolean[N + 1];

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int currentNode = current.to;

            if (visited[currentNode]) continue;
            visited[currentNode] = true;

            for (Edge edge : graph[currentNode]) {
                if (visited[edge.to]) continue;

                if (dist[currentNode] + edge.weight < dist[edge.to]) {
                    dist[edge.to] = dist[currentNode] + edge.weight;
                    pq.offer(new Edge(edge.to, dist[edge.to]));
                }
            }
        }

        return dist[end] == Integer.MAX_VALUE ? -1 : dist[end];
    }
}

3.2. Code Explanation

The above code is an implementation of Dijkstra's algorithm written in Java. Here is an explanation of the main parts:

• Edge Class: A class that defines the edges of the graph. Each edge has a destination node and a weight.
• Graph Initialization: Initializes the graph using an adjacency list approach.
• Priority Queue: Used to explore the current shortest paths, prioritizing nodes with shorter distances.
• Dijkstra's Algorithm: In each iteration, it selects the node with the smallest distance and updates the distances of the connected nodes.

4. Time Complexity

The time complexity of Dijkstra's algorithm varies depending on the use of the priority queue. When using an array as a priority queue, it is O((N + M) log N). Here, N is the number of vertices and M is the number of edges. This algorithm performs well in graphs with many vertices compared to the number of edges.

5. Conclusion

In this post, we explored how to solve the shortest path problem using Dijkstra's algorithm. This algorithm can be applied in various fields, particularly in networks, mapping services, and optimization problems. Understanding and problem-solving abilities related to such algorithms are crucial in coding tests, so it is recommended to practice consistently.