C++ 程序解决无权图的旅行商问题
c++server side programmingprogramming
旅行商问题用于计算覆盖所有城市并返回原点城市的最短路线。此方法用于查找覆盖图的所有节点的最短路径。
这是查找无权图最短路线的程序。
算法
开始 定义一个通用变量 vr = 4。 声明一个整数函数 TSP 来实现旅行商问题。 将图 grph[][] 声明为 2D 矩阵，将变量 p 声明为整数数据类型。 将它们作为参数传递。 将变量 ver 声明为向量数据类型。 for (int i = 0; i < vr; i++) if (i != p) then 调用 push_back(i) 函数存储除源顶点之外的所有顶点的值。 初始化 m_p = INT_MAX 以存储图的最小权重。 do 将 cur_pth、k 声明为整数数据类型。 初始化 cur_pth = 0。 初始化 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) 更新最小权重值。 while (next_permutation(ver.begin(), ver.end()))。 返回 m_p。 将图 grph[][] 声明为整型数据类型的 2D 矩阵。 初始化 grph[][] 图的值。 将变量 p 声明为整型数据类型。 初始化 p = 0。 打印"结果为:"。 打印TSP()函数的返回值。 结束。
示例
#include <bits/stdc++.h>
using namespace std;
#define vr 4
int TSP(int grph[][vr], int p) // 实现旅行商问题。{
vector<int> ver; //
for (int i = 0; i < vr; i++)
if (i != p)
ver.push_back(i);
int m_p = INT_MAX; // 存储图的最小权重
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); // 更新最小权重值
}
while (next_permutation(ver.begin(), ver.end()));
return m_p;
}
int main() {
int grph[][vr] = { { 0, 5, 10, 15 }, //矩阵形式的图的值
{ 5, 0, 20, 30 },
{ 10, 20, 0, 35 },
{ 15, 30, 35, 0 }
};
int p = 0;
cout<< "\n 结果为: "<< TSP(grph, p) << endl;
return 0;
}
输出
结果为: 75
