Java code Issue about interview_ds_algo

[SunilKumarPradhan]

• Handling the Stop Condition: The code increments stop even when the queue is empty, which can lead to more iterations than required.

• Inaccurate Relaxation: The condition if(dis[adjNode] > dis[node]+wt) checks for relaxation, but the code immediately adds a new pair to the priority queue without checking whether the stop limit k has been reached.

• Updating Priority Queue Incorrectly: The priority queue update logic doesn't consider the number of stops taken so far. It merely adds the adjacent node without accounting for the stop limit.

To fix these issues:

1. Correct Stop Condition: Increment the stop counter within the while loop after processing each level of nodes.

2. Check for Stop Limit: Verify whether the number of stops has reached k before adding nodes to the priority queue.

3. Update Priority Queue Correctly: Include the count of stops made so far and use this count to check against the stop limit before adding nodes to the queue.

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        List<ArrayList<Pair>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] flight : flights) {
            adj.get(flight[0]).add(new Pair(flight[2], flight[1]));
        }

        int[] dis = new int[n];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[src] = 0;

        Queue<Pair> pq = new LinkedList<>();
        pq.add(new Pair(0, src));

        int stops = 0;
        while (!pq.isEmpty()) {
            int size = pq.size();
            while (size-- > 0) {
                Pair p = pq.poll();
                int cost = p.cost;
                int node = p.node;

                for (Pair al : adj.get(node)) {
                    int adjNode = al.node;
                    int wt = al.cost;

                    if (stops <= k && dis[node] != Integer.MAX_VALUE && dis[adjNode] > dis[node] + wt) {
                        dis[adjNode] = dis[node] + wt;
                        pq.add(new Pair(dis[adjNode], adjNode));
                    }
                }
            }
            if (stops++ > k) break;
        }

        return dis[dst] == Integer.MAX_VALUE ? -1 : dis[dst];
    }
}

class Pair {
    int cost;
    int node;

    Pair(int cost, int node) {
        this.cost = cost;
        this.node = node;
    }
}

[dhirunand]

Hi @SunilKumarPradhan Have you ran your code ? it's still giving the incorrect output for the test case mentioned (in top)

[princeprakhar]

TRY this

  public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    List<Pair<Integer, Integer>>[] graph = new List[n];

    for (int i = 0; i < n; i++)
      graph[i] = new ArrayList<>();

    for (int[] flight : flights) {
      final int u = flight[0];
      final int v = flight[1];
      final int w = flight[2];
      graph[u].add(new Pair<>(v, w));
    }

    return dijkstra(graph, src, dst, k);
  }

  private int dijkstra(List<Pair<Integer, Integer>>[] graph, int src, int dst, int k) {
    int[][] dist = new int[graph.length][k + 2];
    Arrays.stream(dist).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
    // (d, u, stops)
    Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

    dist[src][k + 1] = 0;
    minHeap.offer(new int[] {dist[src][k + 1], src, k + 1});

    while (!minHeap.isEmpty()) {
      final int d = minHeap.peek()[0];
      final int u = minHeap.peek()[1];
      final int stops = minHeap.poll()[2];
      if (u == dst)
        return d;
      if (stops == 0)
        continue;
      for (Pair<Integer, Integer> pair : graph[u]) {
        final int v = pair.getKey();
        final int w = pair.getValue();
        if (d + w < dist[v][stops - 1]) {
          dist[v][stops - 1] = d + w;
          minHeap.offer(new int[] {dist[v][stops - 1], v, stops - 1});
        }
      }
    }

    return -1;
  }
}

[dhirunand]

Hi Found the simple java BFS level wise traversal

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // Create graph
        List<ArrayList<Pair>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] flight : flights) adj.get(flight[0]).add(new Pair(flight[1], flight[2]));

        int[] dis = new int[n];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[src] = 0;

        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(src, 0)); // cost = 0 to reach src

        int stops = 0;
        while (!q.isEmpty()) {
            int size = q.size();

            while (size-- > 0) {
                Pair pair = q.poll();
                int node = pair.first;
                int cost = pair.second; // cost to reach node
                
                for (Pair al : adj.get(node)) {
                    int adjNode = al.first;
                    int edgeWt = al.second;

                    if (dis[adjNode] > cost + edgeWt) {
                        dis[adjNode] = cost + edgeWt;
                        q.add(new Pair(adjNode, dis[adjNode]));
                    }
                }
            }
            stops++;
            if (stops > k) break;
        }

        return dis[dst] == Integer.MAX_VALUE ? -1 : dis[dst];
    }
``` /