Shortest Path Variant (constrained max hop)

Question

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?

Answer 1

The "best" way to solve your problem is by dynamic programming. This will give you a running time of O(knMaxDegree).

The program is almost identical to the one for the knapsack. The basic idea is that you create a space (node, remaining hops), start at the destination (s,k) and then visit the neighbours of s, and so on.

For a deeper explanation, this problem is known as Constrained Shortest Path.

Answer 2

As indicated by Alberto, I don't think you have any option besides a standard search algorithm. The problem, like you suggest, is that, unlike in a standard Dijkstra algorithm, in this case you cannot dismiss a route just because it has worse added weight than another one to the same node. The algorithm could look like this:

function constrained_shortest_path(g : Graph, s : Node, t : Node, k : Int) : Path
    // queue contains tuples (<weight>, <nodes>, <depth>) and sorts by <weight>
    queue : MinHeap<(Int, List<Node>, Int)>
    queue.add((0, [s], 0))
    while queue is not empty do
        (weight : Int, nodes : List<Node>, depth : Int) := queue.poll()
        last_node = nodes.last()
        if last_node = t
            return nodes
        if depth >= k
            continue
        for adj : Node in g.adjacent_nodes(node)
            adj_weight := g.edge_weight(node, adj)
            queue.add((weight + adj_weight, nodes + [a], depth + 1))
    return []