If you want to make money online : Register now

# Reconstruct the minimal path cost from the delta-stepping algorithm?

, ,
Problem Detail:

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?

###### Asked By : Ivan Felipe Rodríguez

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.

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