I am trying to implement a version of Dijkstra's algorithm for the traveling salesman problem and I found this paper: https://www.researchgate.net/figure/Dijkstras-algorithm-for-many-targets-with-a-pruning-heuristic-An-upper-bound-B-for-d-v_fig2_257428759

I understand the algorithm but I am confused about what 'free' means in this pseudocode. Can anyone explain it to me?

i.e. in the following lines:

if u is free then STOP fl

if v is free then B = min{c, b} fl

A Heuristic for Dijkstra's Algorithm with Many Targets (Pseudocode)

CodePudding user response：

The paper you link to does not seem to deal with the Traveling Salesman Problem, but with bipartite matchings:

Both versions of the problem can be solved by solving n,n=max(|A|,|B|), single-source many-targets shortest-path (SSMTSP) problems in a derived graph, see Section 4.

A free node refers to a node that is not matched with any other node in the bipartite graph. This is stated in section 4 of the linked paper (page label 87), footnote 5:

A node is free if no edge in M is incident to it.

M is defined as the matching that needs to be computed on the previous page.

This algorithm seems to only be useful for this matching problem, which requires that you run it multiple times. It's only an improvement across these multiple runs for bipartite matchings, it is not a standalone algorithm.