Which algorithm is this? 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}
   &amp;f_G = 0 \\
   &amp;f_i = \infty, \forall i ≠ G \\
   &amp;t_{i,j} = \infty, \forall (i, j) \notin T \\
   &amp;t_{i,j} &gt; 0 , \forall (i, j) \in T\\
   &amp;T = \{1, 2, . . . , N − 1, N\}, \quad Ť = \{\emptyset\} \\
   &amp;\text{Do while $T$ is not empty} \\
   &amp;\qquad j^* = \arg\min_{j\in T} f_j \\
   &amp;\qquad \text{for }i \in \mathrm{SCS}(j^*)\\
   &amp;\qquad\qquad f_i  = \min \{f_i , t_{i,j}^* + f_j^*\}\\
   &amp;\qquad \text{Remove $ j^*$ from T, add $j^* $ to Ť} \\
   &amp;\text{Stop while }j^*= S
\end{align}
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.