Java Coding Test Course, Finding Minimum Cost

To prepare for coding tests, it is important to solve various algorithm problems. In this lecture, we will cover the problem of ‘Finding the Minimum Cost’. This problem requires graph theory and dynamic programming techniques. It will further enhance your programming skills.

Problem Description

In the given directed graph, there are several nodes and edges. Each edge has a specific cost. We need to find the minimum cost to move from one node to another. There may be multiple nodes, and there may be several paths between any two nodes.

Input

The first line contains the number of nodes N and the number of edges M (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000)
The next M lines contain edge information. Each edge is given in the format u v c, which means the cost of the edge from node u to v is c. (1 ≤ c ≤ 1000)
The last line contains the starting node S and the target node T.

Output

Print the minimum cost to go from the starting node S to the target node T. If it is not reachable, print -1.

Example Problem

Algorithm Idea

This problem is similar to finding the shortest path in a graph. We can efficiently solve the problem using Dijkstra’s algorithm. This algorithm is optimized for finding the shortest path from one node to another. We will use this algorithm to track the minimum cost from the starting node to the target node.

Description of Dijkstra’s Algorithm

Dijkstra’s algorithm works as follows:

First, initialize the distance from the starting node to each node to infinity, except for the starting node which should be initialized to 0.
Use a priority queue to select the node that can be accessed with the current minimum cost.
Update the costs for adjacent nodes of the chosen node. If a new path has a better cost, update that node and add it to the queue.
Repeat this process until the target node is reached. After processing all nodes, return the final distance to the target node.

Java Code Implementation

    
    import java.util.*;

    public class MinCostPath {
        static class Edge {
            int to, cost;

            Edge(int to, int cost) {
                this.to = to;
                this.cost = cost;
            }
        }

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
        
            int N = sc.nextInt(); // Number of nodes
            int M = sc.nextInt(); // Number of edges
            
            List> graph = new ArrayList<>();
            for (int i = 0; i <= N; i++) {
                graph.add(new ArrayList<>());
            }
        
            for (int i = 0; i < M; i++) {
                int u = sc.nextInt();
                int v = sc.nextInt();
                int c = sc.nextInt();
                graph.get(u).add(new Edge(v, c));
            }
            
            int S = sc.nextInt(); // Starting node
            int T = sc.nextInt(); // Target node
            
            System.out.println(dijkstra(N, graph, S, T));
        }
        
        static int dijkstra(int n, List> graph, int start, int target) {
            int[] dist = new int[n + 1];
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[start] = 0;
        
            PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.cost));
            pq.add(new Edge(start, 0));
        
            while (!pq.isEmpty()) {
                Edge current = pq.poll();
        
                if (current.to == target) {
                    return dist[target];
                }
        
                for (Edge edge : graph.get(current.to)) {
                    if (dist[current.to] + edge.cost < dist[edge.to]) {
                        dist[edge.to] = dist[current.to] + edge.cost;
                        pq.add(new Edge(edge.to, dist[edge.to]));
                    }
                }
            }
        
            return -1; // If not reachable
        }
    }

Code Explanation

In the above code:

First, we get the number of nodes (N) and edges (M) as input.
We input the information for each edge and store the graph in the form of an adjacency list.
We perform initialization tasks for Dijkstra's algorithm. We create a distance array (dist) and set the distance of the starting node to 0.
Using a priority queue, we iteratively update the shortest paths for the adjacent nodes of the current node.
When we reach the target node, we return that distance, and if it is not reachable, we return -1.

Optimizations and Precautions

Dijkstra's algorithm is valid when all edge weights are non-negative. If there are negative edges, we should consider using the Bellman-Ford algorithm. Additionally, when optimizing performance using a priority queue, it is advisable to use a min-heap.

Conclusion

In this lecture, we learned the Dijkstra's algorithm through the 'Finding the Minimum Cost' problem. By practicing solving algorithm problems, we hope you gain confidence in coding tests and further improve your problem-solving skills. In the next session, we will introduce more diverse algorithms.