Which algorithm is this?

Question

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}

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.