Shortest route algorithm - all nodes with known start and end

Question

I'm trying to find out an algorithm that can generate the shortest route, considering the following rules:

• The start and end points are known and fixed
• Visit all nodes only once without repetition

please refer to the example attached here

is there's any algorithm that can be used rather than simply calculating the sum of all possible combinations and selecting the lowest value? which is quite useless if you have big numbers.

Regards,

Answer 1

Graph mentioned in problem is directed, Hence, you should have a look at Travelling Salesman Problem

for detailed explanation and implementation visit geeksforgeeks

However this solution is infeasible i.e. NP-Hard, hence you can also take a look at 2-approximation using MST which might give you an approximation in the answer