2
$\begingroup$

While reading Thorup's Algorithm to solve SSSP problem, I have one point that I can't understand: super distance.

It says: "For each vertex we have a super distance $D(v)\geq d(v)$"

$d(v)$ must refer the shortest distance from origin to $v$, but what is $D$ ?

Is it just a distance value from origin while calculation until $D(v)=d(v)$ ?

$\endgroup$
1
$\begingroup$

It says: "For each vertex we have a super distance $D(v)\geq d(v)$"

"Super" refers to the "$\ge$" relation between $D$ and $d$. In other words, since $D(v)\ge d(v)$ where $d(v)$ is the distance from $v$ to $s$, $D(v)$ is called super distance.

Is it just a distance value from origin while calculation until $D(v)=d(v)$ ?

Correct. It is just a distance that approximates the shortest distance from the source from above, which will become that shortest distance at the time $v$ is moved to $S$, the set of vertices whose distances have been settled.

$\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.