How to find the cheapest flight within K stops

Problem 1: Minimize multi-person debt settlement Given a group of people with multiple loan records, find the minimum number of transactions to settle all debts so everyone's balance is zero. Core idea: First compute each person's net balance, and only focus on those whose net amount is non-zero. Then use backtracking or greedy matching to cancel positive and negative amounts against each other. For example, if someone owes 50 and another is owed 50, a single transaction settles both — minimizing the total number of transactions. Follow-up: If the debt relationships are very complex, involving hundreds of people, can your algorithm still maintain efficiency? Problem 2: Cheapest flights within K stops Given a list of flights with prices, find the lowest-cost path from source to destination within K stops. Approach: This is a classic graph shortest-path problem. You can solve it with dynamic programming where dp[i][k] represents the minimum fare to reach node i within k steps. Alternatively, use a modified Dijkstra's algorithm with a priority queue that also tracks the current number of stops, ensuring you don't exceed K stops while finding the lowest price. Follow-up: If the airline network is very large, or you need to support real-time price updates, how would you optimize?