# 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} &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}

• Welcome to Computer Science! Regarding your MathJax comment, see here for a short reference. – dkaeae Apr 5 at 15:28
• Still bad but it's the best I can do with my limited time atm. Will check on it tomorrow. Thanks for the link – 何承䬠 Apr 5 at 16:05
• @何承䬠 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? – Apass.Jack Apr 5 at 23:44
• That exactly how I took it from my course material @Apass.Jack. Thats why I'm asking here X,D – 何承䬠 Apr 6 at 6:15

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.

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