1
$\begingroup$

I was coding the delta-steppping algorithm from this paper. They describe almost everything about the algorithm but not how to get the path. As an output I am getting the dictionary tent where tent[v] contains the minimal cost to go from $s$ to $v \in V$. How can I retrieve the path of the minimum cost based on this algorithm?

$\endgroup$
  • $\begingroup$ I got kind of lost while coding it, because from the paper they described it to be really simple, so I am wondering if there is an efficient solution rather than just mark the path while running the second routine. Thank you very much for the question. $\endgroup$ – Ivan Felipe Rodríguez Apr 28 '16 at 3:14
1
$\begingroup$

The algorithm that you're implementing is based on the Dijkstra Algorithm, so we can use the same idea to get the path, that is, keep the predecesor data each time you relax the edges (see pred data structure below). Actually, in the same paper, they state where you have to look at in the following method.

enter image description here

However, we need the information of the vertex we are using in the relaxation method, as you know we are comparing these two values, $tent[w]$ vs $tent[v] + Cost[v,w]$. So if after all $tent[v] + Cost[v,w]$ is less than $tent[w]$, we need keep $v$ to say we are going to use the edge $(v,w)$.

Then I suggest you to introduce $v$ as follows:

Replace $Req$ for this definition, $$ Req = \{(w, tent(v) + c(v,w), v)\ :\ v\in B[i] \text{ and } (v,w) \in light[v]\}. $$

Add a third argument to the method relax:

 relax(w,d,v)
    if d < tent[w]:
        pred[w] = v
        ...

And fix all for each with $(w,d,v)\in Req$ and the other.

To retrieve the path from $s$ to $w$, do something like:

for v in V: pred[v] = INF
...
def findpath(w):
  v = w 
  path = []
  while pred[v] is not INF:
     path.append(v)
     v = pred[v]
  path.reverse()
  return path
$\endgroup$
  • $\begingroup$ Since the relax routine is assigning a smaller value to tent[w], Is it right to say that pred[w] has only one item? $\endgroup$ – Ivan Felipe Rodríguez Apr 28 '16 at 3:04
  • $\begingroup$ Indeed, pred[w] is just a value, a vertex but it is not because relax routine is assigning a smaller value to tent[w], it is because, relax a edge $(s, w)$ consists in taking into account another path that pass through $v$ from a s, and go from $v$ to $w$ $\endgroup$ – jonaprieto Apr 28 '16 at 3:11

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.