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}

  • $\begingroup$ Welcome to Computer Science! Regarding your MathJax comment, see here for a short reference. $\endgroup$
    – dkaeae
    Commented Apr 5, 2019 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$
    – 何承䬠
    Commented Apr 5, 2019 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$
    – John L.
    Commented Apr 5, 2019 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$
    – 何承䬠
    Commented Apr 6, 2019 at 6:15

1 Answer 1


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.