Dijkstra Advanced — Modified Dijkstra Patterns (K Stops, States, Constraints)

Beyond Basic Dijkstra

Standard Dijkstra: state = node. Advanced Dijkstra: state = (node, extra_dim).

Problem	State
Cheapest Flights K Stops	(city, stops_used)
Network Delay with Limit	(city, fuel_remaining)
Shortest Path with Obstacles	(r, c, obstacles_removed)
Path with Min Max Edge	(node, current_max)

Pattern: Dijkstra with K Steps (Cheapest Flights)

import heapq

def findCheapestPrice(n, flights, src, dst, k):
    graph = [[] for _ in range(n)]
    for u, v, w in flights:
        graph[u].append((v, w))
    heap = [(0, src, 0)]
    dist = [[float('inf')]*(k+2) for _ in range(n)]
    dist[src][0] = 0
    while heap:
        cost, u, stops = heapq.heappop(heap)
        if u == dst: return cost
        if stops > k: continue
        for v, w in graph[u]:
            nc = cost + w
            if nc < dist[v][stops+1]:
                dist[v][stops+1] = nc
                heapq.heappush(heap, (nc, v, stops+1))
    return -1

JavaScript

function findCheapestPrice(n, flights, src, dst, k) {
    const g=Array.from({length:n},()=>[]);
    for(const[u,v,w]of flights)g[u].push([v,w]);
    const dist=Array.from({length:n},()=>new Array(k+2).fill(Infinity));
    dist[src][0]=0;
    const heap=[[0,src,0]];
    const pop=()=>{let mi=0;for(let i=1;i<heap.length;i++)if(heap[i][0]<heap[mi][0])mi=i;return heap.splice(mi,1)[0];};
    while(heap.length){
        const[cost,u,stops]=pop();
        if(u===dst)return cost; if(stops>k)continue;
        for(const[v,w]of g[u]){const nc=cost+w;if(nc<dist[v][stops+1]){dist[v][stops+1]=nc;heap.push([nc,v,stops+1]);}}
    }
    return -1;
}

Java

import java.util.*;
public int findCheapestPrice(int n,int[][]fl,int src,int dst,int k){
    List<int[]>[]g=new List[n]; for(int i=0;i<n;i++)g[i]=new ArrayList<>();
    for(int[]f:fl)g[f[0]].add(new int[]{f[1],f[2]});
    int[][]dist=new int[n][k+2]; for(int[]r:dist)Arrays.fill(r,Integer.MAX_VALUE/2); dist[src][0]=0;
    PriorityQueue<int[]>pq=new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
    pq.offer(new int[]{0,src,0});
    while(!pq.isEmpty()){int[]top=pq.poll();int cost=top[0],u=top[1],s=top[2];
        if(u==dst)return cost; if(s>k)continue;
        for(int[]nb:g[u]){int nc=cost+nb[1];if(nc<dist[nb[0]][s+1]){dist[nb[0]][s+1]=nc;pq.offer(new int[]{nc,nb[0],s+1});}}}
    return -1;
}

C++

#include <vector>
#include <queue>
#include <climits>
using namespace std;
int findCheapestPrice(int n,vector<vector<int>>&fl,int src,int dst,int k){
    vector<vector<pair<int,int>>> g(n);
    for(auto&f:fl)g[f[0]].push_back({f[1],f[2]});
    vector<vector<int>> dist(n,vector<int>(k+2,INT_MAX/2)); dist[src][0]=0;
    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<>>pq;
    pq.push({0,src,0});
    while(!pq.empty()){auto[cost,u,s]=pq.top();pq.pop();
        if(u==dst)return cost; if(s>k)continue;
        for(auto[v,w]:g[u]){int nc=cost+w;if(nc<dist[v][s+1]){dist[v][s+1]=nc;pq.push({nc,v,s+1});}}}
    return -1;
}

C

/* C: 2D dist array (node x stops), struct-based min-heap */