Normally, Simulated Annealing (SA) is used in TSP problem to find the near-to-optimal solution, and the graph structure in TSP is a complete graph. Therefore, I want to know whether or not I can use SA for finding the shortest path/optimal solution in a non-complete(connected undirected) weighted graph in the 2 dimentional Euclidean space.

If I cannot use SA in this case, could you recommend me a good algorithm for this? *** Note: the weight here is referred to the weight on each node, not edge weight.

Thanks in advanced!

  • $\begingroup$ Simulated Annealing is just an estimation technique, you can use it to solve pretty much any problem. However there's no guarantee the solutions it finds will be any good... $\endgroup$ – BlueRaja - Danny Pflughoeft Sep 25 '17 at 11:28
  • $\begingroup$ @BlueRaja-DannyPflughoeft Thanks for your quick comment. So, could you please recommend me a good shortest path algorithm for this problem? $\endgroup$ – arizamoona Sep 25 '17 at 11:56
  • $\begingroup$ You can use SA. Or there are plenty of approximation algorithms for it, search around. "Non-complete weighted graph" is the usual setup for the problem. $\endgroup$ – BlueRaja - Danny Pflughoeft Sep 25 '17 at 13:07
  • $\begingroup$ @BlueRaja-DannyPflughoeft Thank you so much for your response and advice. I have one more question. Can i use k-means to cluster a non-complete graph like in my case? Because mostly, i only see many people applied it in a complete graph. $\endgroup$ – arizamoona Sep 25 '17 at 13:28
  • $\begingroup$ "Shortest path" is something very different from "shortest TSP tour". You mean the latter, right? $\endgroup$ – adrianN Sep 25 '17 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.