Class RiverTravel

java.lang.Object
topics.dynamic.river.RiverTravel
public class RiverTravel extends Object

Cheaper Travel on the River

A classic routing problem. Given a river with N docks, you can only travel downstream (from dock i to dock j where i < j). You are provided with a tariff matrix indicating the direct cost between any two docks. The goal is to find the absolute minimum cost to travel between all possible pairs of docks, as sometimes taking a sequence of shorter boat trips is cheaper than one long direct trip.

Algorithm Strategy

This is a specialized shortest-path Dynamic Programming approach for a Directed Acyclic Graph (DAG). We build the optimal cost matrix C by iterating backwards. For any pair of docks (i, j), the minimum cost is the lowest value among:

  • Taking the direct trip: Tariff[i][j]
  • Stopping at an intermediate dock k: Cost[i][k] + Cost[k][j]

Complexity Analysis

  • Time Complexity: O(N³) - Three nested loops to evaluate all start points, end points, and intermediate stops.
  • Space Complexity: O(N²) - To store the resulting minimum cost matrix.
Author:
vicegd

  • Constructor Details

    • RiverTravel

      public RiverTravel()

  • Method Details

    • calculateMinimumCosts

      public int[][] calculateMinimumCosts(int[][] tariff)
      Calculates the minimum cost matrix for traveling between all pairs of docks.
      Parameters:
      tariff - The initial matrix containing direct travel fees. Must be an N x N upper triangular matrix.
      Returns:
      A new N x N matrix containing the minimum cost for each (i, j) pair.