重み付けされていないグラフの巡回セールスマン問題を解決するためのC++プログラム

巡回セールスマン問題は、すべての都市をカバーして元の都市に戻るための最短ルートを計算するために使用します。この方法は、グラフのすべてのノードをカバーする最短経路を見つけるために使用されます。

これは、重み付けされていないグラフの最短ルートを見つけるためのプログラムです。

アルゴリズム

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