Traveling Saleperson -shortest path for specific givven points
Budget: $8 – $15 USD
I want to customize this code to find the shortest path between given points
the code will read a matrix with weights values and give us the shortest bath value between given points.
t an array of points that user enter
the current code passing the first point in the array t and the last point
but I want to make my code calculate the shortest path between all the points in the array t (the order of points visited does not matter)
and the code can visit other points but it is necessary to visit the given points in the array t
here is the code to be customized>>
int main()
{
.
.
int s = t[1] - '0', m = t[(strlen(t) - 1)] - '0';
// marking the source as visited
visited[s] = 1;
int result;
result = minimumCostSimplePath(s, m, visited, adjMatrix_dest, len);
printf("\n\nMinimum cost is %d\n ", result);
}
int minimumCostSimplePath(int u, int destination, bool visited[], int **graph, int len)
{
// check if we find the destination
// then further cost will be 0
if (u == destination)
return 0;
// marking the current node as visited
visited[u] = 1;
int ans = INFINITY;
// traverse through all
// the adjacent nodes
for (int i = 0; i < len; i++)
{
if (graph[u][i] != INFINITY && !visited[i])
{
// cost of the further path
int curr = minimumCostSimplePath(i, destination, visited, graph, len);
// check if we have reached the destination
if (curr < INFINITY)
{
// Taking the minimum cost path
ans = (ans > graph[u][i] + curr) ? graph[u][i] + curr : ans;
}
}
}
// unmarking the current node
// to make it available for other
// simple paths
visited[u] = 0;
// returning the minimum cost
return ans;
}
for example if int arr={2,1,3} (maximum arr length is 6) the function cost will calculate the shortest path between the vertexes2,1,3 (no matter the order between them) or return -1 if there is no existing path.
No need to think about complications. In this problem exponential runtime complexity for the best solution.
the code will read a matrix with weights values and give us the shortest bath value between given points.
t an array of points that user enter
the current code passing the first point in the array t and the last point
but I want to make my code calculate the shortest path between all the points in the array t (the order of points visited does not matter)
and the code can visit other points but it is necessary to visit the given points in the array t
here is the code to be customized>>
int main()
{
.
.
int s = t[1] - '0', m = t[(strlen(t) - 1)] - '0';
// marking the source as visited
visited[s] = 1;
int result;
result = minimumCostSimplePath(s, m, visited, adjMatrix_dest, len);
printf("\n\nMinimum cost is %d\n ", result);
}
int minimumCostSimplePath(int u, int destination, bool visited[], int **graph, int len)
{
// check if we find the destination
// then further cost will be 0
if (u == destination)
return 0;
// marking the current node as visited
visited[u] = 1;
int ans = INFINITY;
// traverse through all
// the adjacent nodes
for (int i = 0; i < len; i++)
{
if (graph[u][i] != INFINITY && !visited[i])
{
// cost of the further path
int curr = minimumCostSimplePath(i, destination, visited, graph, len);
// check if we have reached the destination
if (curr < INFINITY)
{
// Taking the minimum cost path
ans = (ans > graph[u][i] + curr) ? graph[u][i] + curr : ans;
}
}
}
// unmarking the current node
// to make it available for other
// simple paths
visited[u] = 0;
// returning the minimum cost
return ans;
}
for example if int arr={2,1,3} (maximum arr length is 6) the function cost will calculate the shortest path between the vertexes2,1,3 (no matter the order between them) or return -1 if there is no existing path.
No need to think about complications. In this problem exponential runtime complexity for the best solution.