3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Have you tried an appropriate modification to Dijkstra's algorithm or to Bellman-Ford? Have you tried using dynamic programming? $\endgroup$ – D.W. Oct 28 '15 at 3:34
  • $\begingroup$ @D.W. yes the above is my modification of djikstra (that doesnt work) $\endgroup$ – iluvAS Oct 28 '15 at 3:38
  • 1
    $\begingroup$ What is the question here? Should we debug your algorithm, or give you any algorithm for the problem? $\endgroup$ – Raphael Jul 14 '16 at 6:06
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jul 14 '16 at 6:06
  • $\begingroup$ Idea: add the sum of all weights $S$ to each edge weight. Find a shortest path. Does it have weight $< (k+1)S$? $\endgroup$ – Raphael Jul 14 '16 at 6:08
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ At each step of the DP you take the best decision given your state, there you need the weights. In the following paper they explain the process in excruciating detail, it is even implemented: doc.utwente.nl/55706/1/JFP_shortest_path.pdf $\endgroup$ – Rostov Jul 15 '16 at 6:48
0
$\begingroup$

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 []
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.