โปรแกรม 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