INPUT: directed non negative weighted graph, s, t, k
OUTPUT: SSSP from s to t where the path has $\leq k$ vertices
heap.add(s,0) where s is vertex and 0 is weight and heap is minheap depth[s] = 1; do c = heap.poll(); SSSP[c] = c.weight if(depth[c] >= k) continue loop; for v in c's adjacent vertices if SSSP[v] is infinite heap.add(v, SSSP[c] + weight c to v) depth[v] = depth[c] + 1; else if getHeapNode(v).weight > SSSP[c] + weight c to v getHeapNode(v).weight = SSSP[c] + weight c to v heapify/shiftup depth[v] = depth[c] + 1; while(!heap.isEmpty()) ans = SSSP[t];
Here is my approach and it doesn't work because I think there can be a case where a vertex that has been polled from the heap that exceeds $k$ when later is revisted by a longer (greater weight) path BUT at depth $\leq k-2$. This means that the neighbour of the polled vertex is reachable by the slower path but is not computable as the vertex has already been polled. I don't think this is the only criteria for max-k hops constrained shortest path. How should i go about doing this?