Java Coding Test Course, Finding the Shortest Path

In this lecture, we will cover the problem of “finding the shortest path,” which often appears in algorithm tests for employment. The shortest path problem is an important topic in graph theory and is very useful when finding the optimal route in complex network environments. We will discuss how to solve this problem using Java.

Problem Description

This is the problem of finding the shortest path from a specific starting point to a specific destination in a given graph that satisfies the following conditions.

• The graph is directed and has weighted edges.
• The total number of nodes is V, and the total number of edges is E.
• The nodes of the graph are numbered from 1 to V.

Example Problem

When given the following graph as input:

5 8          // 5 nodes, 8 edges
1 2 2       // weight 2 from node 1 to node 2
1 3 3       // weight 3 from node 1 to node 3
2 3 1       // weight 1 from node 2 to node 3
2 4 1       // weight 1 from node 2 to node 4
3 4 6       // weight 6 from node 3 to node 4
3 5 1       // weight 1 from node 3 to node 5
4 5 2       // weight 2 from node 4 to node 5
1 5 10      // weight 10 from node 1 to node 5

When the starting point is node 1 and the destination point is node 5, find the weight of the shortest path.

Problem Analysis

This problem can be solved using Dijkstra’s algorithm. Dijkstra’s algorithm is a method for finding the shortest path from one node to all other nodes in a given graph. This algorithm follows these steps:

1. Set the starting node to 0 and all other nodes to infinity.
2. Update the distances to adjacent nodes.
3. Select the node with the shortest distance to determine the path.
4. Repeat this process until all nodes have been selected.

Algorithm Implementation

Now, let’s implement Dijkstra’s algorithm in Java.

import java.util.*;

public class DijkstraAlgorithm {
    static class Edge {
        int node;
        int weight;

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

    static final int INF = Integer.MAX_VALUE;
    static List> graph = new ArrayList<>();
    static int[] dist;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int V = scanner.nextInt(); // Number of nodes
        int E = scanner.nextInt(); // Number of edges

        // Initialize the graph
        for (int i = 0; i <= V; i++) {
            graph.add(new ArrayList<>());
        }

        // Input edges
        for (int i = 0; i < E; i++) {
            int from = scanner.nextInt();
            int to = scanner.nextInt();
            int weight = scanner.nextInt();
            graph.get(from).add(new Edge(to, weight));
        }

        int start = 1; // Starting node
        dist = new int[V + 1];
        visited = new boolean[V + 1];

        // Initialize distances
        Arrays.fill(dist, INF);
        dist[start] = 0;

        // Run Dijkstra's algorithm
        dijkstra(start);

        // Output shortest distance
        int end = 5; // Destination node
        System.out.println("Shortest distance: " + dist[end]);
    }

    private static void dijkstra(int start) {
        PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.offer(new Edge(start, 0));

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

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

            for (Edge edge : graph.get(currentNode)) {
                if (dist[currentNode] + edge.weight < dist[edge.node]) {
                    dist[edge.node] = dist[currentNode] + edge.weight;
                    pq.offer(new Edge(edge.node, dist[edge.node]));
                }
            }
        }
    }
}

Code Explanation

The DijkstraAlgorithm class above implements Dijkstra's algorithm. Here is an explanation of each part:

• Edge class: A class that stores nodes and weights.
• graph: Represents the graph in adjacency list format.
• dist: An array representing the shortest distance to each node.
• visited: Indicates whether a node has been visited.
• dijkstra(): A method implementing Dijkstra's algorithm, which uses a priority queue to update the shortest distances.

Results and Execution

When you run the code above, you can calculate the shortest distance from node 1 to node 5 for the given input graph. The result will be as follows:

Shortest distance: 3

Conclusion

In this lecture, we explored how to solve the shortest path problem using Java. Dijkstra's algorithm is used in various applications and is very useful when dealing with complex graphs. Through this problem, we learned the basic concepts of graph theory and how to implement them in Java. In the future, we will also explore more challenging algorithm problems and various graph traversal techniques.