Shortest Paths Problems

Problem: Shortest Path with Maximum Distance from Fire

The ant can move in four directions: up, down, left, or right. The goal is to find the shortest path from (0, 0) to (m-1, n-1) while ensuring that the ant stays as far away from the fire as possible. Specifically, the path should maximize the minimum distance from any fire cell along the way.

Constraints

The grid will have dimensions m x n, where 1 <= m, n <= 100.
The ant cannot travel through cells with fire (F).
The ant can move in four directions: up, down, left, or right.
If no valid path exists, return -1.
The distance from a cell to the fire is the Manhattan distance to the nearest fire cell.

Input

A 2D grid of characters (F or .) representing the map.
The starting position is (0, 0), and the destination is (m-1, n-1).

Output

Return the length of the shortest path from (0, 0) to (m-1, n-1) while maximizing the minimum distance from any fire cell.
If no such path exists, return -1.

function shortestPathWithMaxDistanceFromFire(grid) {
  const m = grid.length;
  const n = grid[0].length;

  // Directions for moving up, down, left, right
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  // Step 1: Precompute the distance of each cell from the nearest fire
  const fireDistance = new Array(m).fill().map(() => new Array(n).fill(Infinity));
  const queue = [];

  // Initialize the queue with all fire positions
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 'F') {
        queue.push([i, j]);
        fireDistance[i][j] = 0;
      }
    }
  }

  // BFS to compute the distance from each fire
  while (queue.length > 0) {
    const [x, y] = queue.shift();
    for (const [dx, dy] of directions) {
      const nx = x + dx;
      const ny = y + dy;
      if (nx >= 0 && nx < m && ny >= 0 && ny < n && fireDistance[nx][ny] === Infinity) {
        fireDistance[nx][ny] = fireDistance[x][y] + 1;
        queue.push([nx, ny]);
      }
    }
  }

  // Step 2: Find the shortest path with maximum distance from fire
  const visited = new Array(m).fill().map(() => new Array(n).fill(false));
  const priorityQueue = [];

  // Start from (0, 0) with distance 0 and the distance from fire at that cell
  priorityQueue.push([0, 0, 0, fireDistance[0][0]]);
  visited[0][0] = true;

  while (priorityQueue.length > 0) {
    priorityQueue.sort((a, b) => b[3] - a[3]); // Sort by distance from fire (max first)
    const [x, y, dist, fireDist] = priorityQueue.pop();

    // If we reach the destination, return the distance
    if (x === m - 1 && y === n - 1) {
      return dist;
    }

    // Explore all four directions
    for (const [dx, dy] of directions) {
      const nx = x + dx;
      const ny = y + dy;
      if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] === '.') {
        visited[nx][ny] = true;
        priorityQueue.push([nx, ny, dist + 1, fireDistance[nx][ny]]);
      }
    }
  }

  // If no path is found
  return -1;
}

// Example usage:
const grid = [
  ['.', 'F', '.', '.'],
  ['.', '.', '.', 'F'],
  ['F', '.', '.', '.'],
  ['.', '.', 'F', '.']
];

console.log(shortestPathWithMaxDistanceFromFire(grid)); // Output: 6

const grid2 = [
  ['.', '.', '.', '.'],
  ['.', 'F', '.', '.'],
  ['.', '.', '.', '.'],
  ['.', '.', '.', '.']
];

console.log(shortestPathWithMaxDistanceFromFire(grid2)); // Output: 5

Problem: Optimal Apartment Location

Description

You are planning to move to a new city and want to find the optimal apartment location. The city is represented as a 2D grid, where each cell can be:

A potential apartment location.
A key location (e.g., gym, office, restaurant, etc.).
An obstacle (e.g., park, lake, etc.) that cannot be traversed.

Your goal is to find the apartment location that is closest to all key locations (e.g., gym, office, restaurant, etc.). The optimal apartment is the one that minimizes the total distance (or travel time) to all key locations.

Constraints

The grid will have dimensions m x n, where 1 <= m, n <= 100.
You can move in four directions: up, down, left, or right.
Obstacles are represented by X, and you cannot travel through them.
Key locations are represented by unique identifiers (e.g., G for gym, O for office, R for restaurant, etc.).
Apartment locations are represented by A.
If no valid apartment location exists, return -1.

Input

A 2D grid of characters representing the city map. The grid contains:
- A: Potential apartment locations.
- G, O, R, etc.: Key locations (gym, office, restaurant, etc.).
- X: Obstacles that cannot be traversed.
- .: Empty spaces that can be traversed.

Output

Return the coordinates (x, y) of the optimal apartment location that minimizes the total distance to all key locations.
If no valid apartment location exists, return -1.

function findOptimalApartment(grid, keyLocations) {
    const m = grid.length;
    const n = grid[0].length;
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // Up, Down, Left, Right

    // Initialize distance grids for each key location
    const distanceGrids = keyLocations.map(([x, y]) => {
        const distanceGrid = new Array(m).fill().map(() => new Array(n).fill(Infinity));
        const queue = [[x, y]];
        distanceGrid[x][y] = 0;

        // BFS to compute distances from this key location
        while (queue.length > 0) {
            const [cx, cy] = queue.shift();
            for (const [dx, dy] of directions) {
                const nx = cx + dx;
                const ny = cy + dy;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] !== 'X' && distanceGrid[nx][ny] === Infinity) {
                    distanceGrid[nx][ny] = distanceGrid[cx][cy] + 1;
                    queue.push([nx, ny]);
                }
            }
        }
        return distanceGrid;
    });

    // Find the apartment with the smallest total distance to all key locations
    let minTotalDistance = Infinity;
    let optimalApartment = null;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 'A') { // 'A' represents an apartment
                let totalDistance = 0;
                for (const distanceGrid of distanceGrids) {
                    totalDistance += distanceGrid[i][j];
                }
                if (totalDistance < minTotalDistance) {
                    minTotalDistance = totalDistance;
                    optimalApartment = [i, j];
                }
            }
        }
    }

    return optimalApartment;
}

// Example usage
const grid = [
    ['.', '.', '.', '.', '.'],
    ['.', 'G', '.', 'X', '.'],
    ['.', '.', 'A', '.', '.'],
    ['.', 'X', '.', 'O', '.'],
    ['.', '.', '.', '.', 'R']
];

const keyLocations = [
    [1, 1], // Gym (G)
    [3, 3], // Office (O)
    [4, 4]  // Restaurant (R)
];

const optimalApartment = findOptimalApartment(grid, keyLocations);
console.log("Optimal Apartment Location:", optimalApartment); // Output: [2, 2]

Minimum Combined Travel Cost for Alice and Bob

You are given a graph of cities where each vertex represents a city, and the edges represent the connectivity between two cities. The cost to travel from one city to another connected by a single edge is 1 unit. Two friends, Alice and Bob, live in two different cities and want to reach a destination city to attend a concert. Both Alice and Bob plan to take cabs from their respective cities to reach the destination. They may decide to share a cab at some point to minimize the total cost of traveling to the destination city.

Your task is to find the minimum combined cost for both Alice and Bob to reach the destination city.

Example

Consider the following graph:

A - B
|   |
D - C
|   |
E - F

Alice's starting city: A
Bob's starting city: E
Destination city: C

Explanation:

Alice travels from A to D (cost = 1).
Bob travels from E to D (cost = 1).
Both Alice and Bob share a cab from D to C (cost = 1).

Total cost = 1 + 1 + 1 = 3

Input

A graph represented as an adjacency list or matrix.
The starting cities for Alice and Bob.
The destination city.

Output

The minimum combined cost for Alice and Bob to reach the destination city.

Constraints

The graph is undirected and unweighted (each edge has a cost of 1 unit).
Alice and Bob can share a cab at any point during their journey.

Approach

Use Breadth-First Search (BFS) to compute the shortest distance from Alice's starting city to all other cities.
Use BFS to compute the shortest distance from Bob's starting city to all other cities.
Use BFS to compute the shortest distance from the destination city to all other cities.
Iterate through all cities to find the optimal meeting point where the combined cost of Alice and Bob traveling to the meeting point and then sharing a cab to the destination is minimized.

function minTravelCost(edges, alice, bob, destination) {
  // Build adjacency list for the graph
  let graph = new Map();

  edges.forEach(([u, v]) => {
    if (!graph.has(u)) graph.set(u, []);
    if (!graph.has(v)) graph.set(v, []);
    graph.get(u).push(v);
    graph.get(v).push(u);
  });

  // BFS function to calculate shortest distances from a given start city
  function bfs(start) {
    let queue = [[start, 0]];
    let distances = new Map();
    distances.set(start, 0);

    while (queue.length > 0) {
      let [city, dist] = queue.shift();
      for (let neighbor of (graph.get(city) || [])) {
        if (!distances.has(neighbor)) {
          distances.set(neighbor, dist + 1);
          queue.push([neighbor, dist + 1]);
        }
      }
    }
    return distances;
  }

  // Get shortest paths from Alice, Bob, and the destination
  let distFromAlice = bfs(alice);
  let distFromBob = bfs(bob);
  let distFromDestination = bfs(destination);

  // Find the minimum cost meeting point
  let minCost = Infinity;
  for (let city of graph.keys()) {
    if (distFromAlice.has(city) && distFromBob.has(city) && distFromDestination.has(city)) {
      let totalCost = distFromAlice.get(city) + distFromBob.get(city) + distFromDestination.get(city);
      minCost = Math.min(minCost, totalCost);
    }
  }

  return minCost;
}

// Example usage:
const edges = [['A', 'B'], ['A', 'D'], ['B', 'C'], ['D', 'C'], ['D', 'E'], ['E', 'F'], ['F', 'C']];
console.log(minTravelCost(edges, 'A', 'E', 'C')); // Output: 3

Find the Nearest Favorite City Using Dijkstra's Algorithm with BFS

Problem Statement

You are given a set of directed connections (weighted edges) between cities. Additionally, you have a list of favorite cities. Given a starting city, find the nearest favorite city using Dijkstra's algorithm implemented with BFS-style traversal.

Input

n: Number of cities.
edges: A list of directed edges, where each edge is represented as [city1, city2, weight].
favoriteCities: A set containing the names (or indices) of favorite cities.
startCity: The city from which the search begins.

Output

The nearest favorite city & min distance from startCity. If no favorite city is reachable, return -1.

function dijkstra(graph, start, favoriteCities) {
  const distances = {};
  const pq = new MinPriorityQueue();

  // Initialize distances
  for (const city in graph) {
    distances[city] = Infinity;
  }
  distances[start] = 0;
  pq.enqueue(start, 0);

  while (!pq.isEmpty()) {
    const { element: currentCity, priority: currentDistance } = pq.dequeue();

    if (currentDistance > distances[currentCity]) continue;

    for (const neighbor in graph[currentCity]) {
      const distance = currentDistance + graph[currentCity][neighbor];

      if (distance < distances[neighbor]) {
        distances[neighbor] = distance;
        pq.enqueue(neighbor, distance);
      }
    }
  }

  // Find the nearest favorite city
  let nearestFavoriteCity = null;
  let minDistance = Infinity;

  for (const city of favoriteCities) {
    if (distances[city] < minDistance) {
      minDistance = distances[city];
      nearestFavoriteCity = city;
    }
  }

  return [nearestFavoriteCity, minDistance];
}

// Example usage:
const graph = {
  'A': { 'B': 1, 'C': 4 },
  'B': { 'A': 1, 'C': 2, 'D': 5 },
  'C': { 'A': 4, 'B': 2, 'D': 1 },
  'D': { 'B': 5, 'C': 1 }
};

const favoriteCities = ['C', 'D'];
const startCity = 'A';

const nearestFavoriteCity = dijkstra(graph, startCity, favoriteCities);
console.log(`The nearest favorite city from ${startCity} is ${nearestFavoriteCity}`);
/* 
The nearest favorite city from A is C,3
*/

Problem: Shortest Path with Maximum Distance from Fire​

Constraints​

Input​

Output​

Problem: Optimal Apartment Location​

Description​

Constraints​

Input​

Output​

Minimum Combined Travel Cost for Alice and Bob​

Example​

Explanation:​

Input​

Output​

Constraints​

Approach​

Find the Nearest Favorite City Using Dijkstra's Algorithm with BFS​

Problem Statement​

Input​

Output​

Problem: Shortest Path with Maximum Distance from Fire

Constraints

Input

Output

Problem: Optimal Apartment Location

Description

Constraints

Input

Output

Minimum Combined Travel Cost for Alice and Bob

Example

Explanation:

Input

Output

Constraints

Approach

Find the Nearest Favorite City Using Dijkstra's Algorithm with BFS

Problem Statement

Input

Output