If you want to make money online : Register now

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

, , No Comments
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
Answered By : jonaprieto

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 
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56627

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback