数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会科学
时尚研究
法律研究一个 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
更新时间：2019-07-30
3K+ 次查看
广告