가중되지 않은 그래프에 대한 순회 세일즈맨 문제를 해결하기 위한 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