1
$\begingroup$

I'm looking for someone who can tell me which algorithm this is and help me to clearify what the variable mean.

  • $g_j$ : the shortest path length from $1$ to $j$

  • $t_{i,j}$: the length from $i$ to $j$

  • $\mathrm{SCS}$: successive set

  • $S$: Start node, $G$: Goal node

\begin{align} &f_G = 0 \\ &f_i = \infty, \forall i ≠ G \\ &t_{i,j} = \infty, \forall (i, j) \notin T \\ &t_{i,j} > 0 , \forall (i, j) \in T\\ &T = \{1, 2, . . . , N − 1, N\}, \quad Ť = \{\emptyset\} \\ &\text{Do while $T$ is not empty} \\ &\qquad j^* = \arg\min_{j\in T} f_j \\ &\qquad \text{for }i \in \mathrm{SCS}(j^*)\\ &\qquad\qquad f_i = \min \{f_i , t_{i,j}^* + f_j^*\}\\ &\qquad \text{Remove $ j^*$ from T, add $j^* $ to Ť} \\ &\text{Stop while }j^*= S \end{align}

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! Regarding your MathJax comment, see here for a short reference. $\endgroup$ – dkaeae Apr 5 at 15:28
  • $\begingroup$ Still bad but it's the best I can do with my limited time atm. Will check on it tomorrow. Thanks for the link $\endgroup$ – 何承䬠 Apr 5 at 16:05
  • $\begingroup$ @何承䬠 Should "$f_i = \min (f_i , t_{i,j}^* + f_j^*)$" be "$f_i = \min (f_i , t_{i,j} + f_j^*)$", since $t_{i,j}^*$ is not introduced? $\endgroup$ – Apass.Jack Apr 5 at 23:44
  • $\begingroup$ That exactly how I took it from my course material @Apass.Jack. Thats why I'm asking here X,D $\endgroup$ – 何承䬠 Apr 6 at 6:15
2
$\begingroup$

It looks like a Dijkstra algorithm to me.

I see the algorithm begins at the "do while" line and everything before are the input for the algorithm. With your clue that G is the goal node, and $t_{i,j}$ are lengths, it is easy to see $f_i$ is the distance from $i$ to G as we know so far within the loop.

So the algorithm means the following:

  • Every iteration, we find the node $j^*$ within T that has min distance to G
  • Then we scan each of its neighbor $i$, update their distance to G
    • update rule: they reach G with traversing $j^*$ or without (i.e., the old $f_i$), so min of these two will be the new known min distance to G
  • After this scan, all nodes that can possibly reach G via $j^*$ are updated. And we remove $j^*$ from T, meaning that in the future, any other node (not neighbor to $j^*$) to reach G via $j^*$ should only be via one of its neighbor $i$

Here the $t_{i,j}$ are positive, so that adding to $f_{j^*}$ can only increase the distance. And hence all $f_i$ will only be decreasing in each iteration. In this case, this algorithm is a dynamic programming by iteratively reducing the problem to a smaller set of nodes until a solution is found.

$\endgroup$
  • $\begingroup$ @Apass.Jack You're right. I overlooked. $\endgroup$ – Adrian Tam Apr 5 at 18:42
  • $\begingroup$ Thanks alot. It finally makes sense $\endgroup$ – 何承䬠 Apr 6 at 6:16

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.