# No Dijkstra and no BFS? What else is there?

So, this is the scenario I have a graph with 7 points (say A to G) all interconnected (full mesh), and I want the best path to traverse all points starting from A and ending on G, but there are a couple of... caveats:

1.- The weight from A to B is not necessarily the same as the weight from B to A, and

2.- Some weights can be negative

Is there an algorithm that could help solve this problem?

• Maybe self organizing maps could be used to make a guess, but getting the optimal path is unlikely. May 17 at 1:46
• @Galen TSPs much larger than this are routinely solved to optimality. May 17 at 2:42
• @RobPratt I'm surprised. Globally? Or just local optima? May 17 at 3:42
• @Galen Yes, globally. May 17 at 12:12

Unfortunately, you are dealing with an $$\mathsf{NP}$$-hard problem, which is called the Traveling Salesman Problem. This means there is no efficient way to solve your problem.

Thankfully, the graph is relatively small, so brute force can be done in realistic time.

A reduction which you need to do is make all the edges' weights nonnegative. This can be done by adding a constant to all edges.

• I don't think he needs to add anything. Let the particle traverse the entire plot for 1000000 times, with the negative constants and find the minimum. May 16 at 21:10
• I forgot to add that vertices can be revisited at any time, so yeah, brute-forcing sounds like the way to go. That, plus negative weights, makes it a bit different from the TSP I guess. May 16 at 22:02

If you introduce a dummy node adjacent to only A and G, you have an asymmetric traveling salesman problem on a directed graph with 8 nodes, which can be converted to a symmetric traveling salesman problem on an undirected graph with 16 nodes.

For directed or undirected TSP, you can have negative weights.

If you post the data, I'll find an optimal solution.