INPUT: directed non negative weighted graph, s, t, k
OUTPUT: SSSP from s to t where the path has $\leq k$ vertices
MY PROGRESS:
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?