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