stellarbackupnode5.cfd

Minimum

Written by

pw

in

Algorithms, data-sd-animate=

Introduction

This article explains algorithms for finding minimum cost solutions in Java, focusing on clear concepts, practical patterns, and working code. It covers problem framing, common algorithmic approaches, complexity trade-offs, and a complete Java implementation for a typical minimum-cost path problem.

Problem framing

A “minimum cost finder” typically means: given a graph, grid, or sequence with costs on nodes or edges, find a path or selection whose total cost is minimal subject to constraints. Common variants:

  • Shortest path in weighted graphs (single-source, single-pair).
  • Minimum cost path in a grid (movement constraints).
  • Minimum cost matching or flow.
  • Minimum cost to transform/construct (dynamic programming).

We’ll demonstrate solutions for two widely used cases:

  1. Shortest path in a weighted directed graph (Dijkstra, Bellman–Ford).
  2. Minimum-cost path in a 2D grid with nonnegative costs (Dijkstra / DP).

1) Shortest path in a weighted graph

When edge weights are nonnegative: use Dijkstra’s algorithm (O(E log V) with a binary heap).
When negative edges may exist (but no negative cycles): use Bellman–Ford (O(VE)).

Key ideas:

  • Maintain distance[] from source to every node.
  • Use a priority queue to expand the closest unsettled node (Dijkstra).
  • Relax edges: if distance[u] + w(u,v) < distance[v], update.

Java implementation (Dijkstra)

java
import java.util.*;
class Edge { int to; int weight; Edge(int t,int w){to=t;weight=w;} }
public class MinCostDijkstra {static int INF = Integer.MAXVALUE / 4;    public static int[] dijkstra(ListEdge>> g, int src) {        int n = g.size();        int[] dist = new int[n];        Arrays.fill(dist, INF);        dist[src] = 0;        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));        pq.offer(new int[]{0, src});        boolean[] seen = new boolean[n];        while (!pq.isEmpty()) {            int[] cur = pq.poll();            int d = cur[0], u = cur[1];            if (seen[u]) continue;            seen[u] = true;            for (Edge e : g.get(u)) {                int v = e.to, w = e.weight;                if (dist[v] > d + w) {                    dist[v] = d + w;                    pq.offer(new int[]{dist[v], v});                }            }        }        return dist;    }
    // Example usage omitted for brevity.}

When negative edges exist, use Bellman–Ford:

    &]:pl-6” data-streamdown=“unordered-list”>

  • Initialize dist[src]=0, repeat V-1 times: for every edge (u,v,w) relax v.
  • Optionally detect negative cycles by checking one more relaxation pass.

2) Minimum-cost path in a 2D grid

Problem: Given an m×n grid of nonnegative costs, find minimal cost from top-left to bottom-right, moving 4-directions or only right/down.

If only right/down: dynamic programming with O(mn) time, O(n) or O(1) extra space.
If four-direction moves allowed and costs nonnegative: treat cells as graph nodes and run Dijkstra.

Right/down DP (Java)

java
public class MinCostGrid {    public static int minPathSum(int[][] grid) {        int m = grid.length, n = grid[0].length;        int[] dp = new int[n];        dp[0] = grid[0][0];        for (int j = 1; j < n; j++) dp[j] = dp[j-1] + grid[0][j];        for (int i = 1; i < m; i++) {            dp[0] += grid[i][0];            for (int j = 1; j < n; j++) {                dp[j] = Math.min(dp[j], dp[j-1]) + grid[i][j];            }        }        return dp[n-1];    }}

Complexity comparison

  • Dijkstra (binary heap): O(E log V). For dense graphs this approaches O(V^2).
  • Bellman–Ford: O(VE).
  • Grid DP (right/down): O

Your email address will not be published. Required fields are marked *

More posts