सी++ प्रोग्राम टू सॉल्व टु ट्रैवलिंग सेल्समैन प्रॉब्लम फॉर अनवेटेड ग्राफ़

सभी शहरों को कवर करने और मूल शहर में वापस लौटने के लिए सबसे छोटे मार्ग की गणना करने के लिए ट्रैवलिंग सेल्समैन समस्या का उपयोग करें। इस विधि का उपयोग ग्राफ के सभी नोड्स को कवर करने के लिए सबसे छोटा रास्ता खोजने के लिए किया जाता है।

यह बिना भारित ग्राफ़ का सबसे छोटा मार्ग खोजने का कार्यक्रम है।

एल्गोरिदम

Begin
   Define a variable vr = 4 universally.
   Declare an integer function TSP to implement Travelling salesman Problem.
   Declare a graph grph[][] as a 2D matrix and variable p to the integer datatype.
   Pass them as a parameter.
   Declare variable ver to the vector datatype.
   for (int i = 0; i < vr; i++)
      if (i != p) then
         Call push_back(i) function to store the value of all vertex except source vertex.
         Initialize m_p = INT_MAX to store minimum weight of a graph.
      do
         Declare cur_pth, k to the integer datatype.
            initialize cur_pth = 0.
            initialize k = p.
         for (int i = 0; i < ver.size(); i++)
            cur_pth += grph[k][ver[i]].
            k = ver[i].
         cur_pth += grph[k][p].
         m_p = min(m_p, cur_pth) to update the value of minimum weight.
         while (next_permutation(ver.begin(), ver.end())).
         Return m_p.
   Declare a graph grph[][] as a 2D matrix to the integer datatype.
      Initialize values of grph[][] graph.
   Declare variable p to the integer datatype.
      Initialize p = 0.
   Print “The result is: ”.
   Print the return value of TSP() function.
End.

उदाहरण

#include <bits/stdc++.h>
using namespace std;
#define vr 4
int TSP(int grph[][vr], int p) // implement traveling Salesman Problem. {
   vector<int> ver; //
   for (int i = 0; i < vr; i++)
      if (i != p)
         ver.push_back(i);
         int m_p = INT_MAX; // store minimum weight of a graph
   do {
      int cur_pth = 0;
      int k = p;
      for (int i = 0; i < ver.size(); i++) {
         cur_pth += grph[k][ver[i]];
         k = ver[i];
      }
      cur_pth += grph[k][p];
      m_p = min(m_p, cur_pth); // to update the value of minimum weight
   }
   while (next_permutation(ver.begin(), ver.end()));
   return m_p;
}
int main() {
   int grph[][vr] = { { 0, 5, 10, 15 }, //values of a graph in a form of matrix
      { 5, 0, 20, 30 },
      { 10, 20, 0, 35 },
      { 15, 30, 35, 0 }
   };
   int p = 0;
   cout<< "\n The result is: "<< TSP(grph, p) << endl;
   return 0;
}

आउटपुट

The result is: 75