中的最短路径算法 - 与已知的开始和结束

-1

我试图找出一种算法，可以生成最短的路线，考虑到以下规则的所有节点：中的最短路径算法 - 与已知的开始和结束

的起点和终点是已知的，固定的
访问所有节点只有一次没有重复

请参考附件here

的例子是有任何的算法可以使用它而不是简单地计算所有可能组合的总和并选择最低值？如果你有大数字，这是无用的。

的问候，在问题中提到

来源

2017-04-23 lightworks

可能的重复[优化TSP算法]（http：// stac koverflow.com/questions/7159259/optimized-tsp-algorithms） –

问题基本上是TSP。虽然TSP的销售人员在同一节点上开始和结束，但您可以将问题转化为它 - 添加一个额外的节点并将其从开始和结束的距离分配为较小，并将其距每个其他节点的距离设置为无穷大。然后，从额外节点开始和结束的任何最优TSP路由将是解决问题的方案（或解决方案的反面）。这是一个极难解决的问题。 –

-1

图是定向的，因此，你应该看看Travelling Salesman Problem

进行详细的解释和执行访问geeksforgeeks

但是这种解决方案是不可行的，即NP难，因此你也可以看看2-approximation using MST这可能会给你一个近似的答案

来源

2017-04-23 11:31:50 Ani

Dijkstra的算法用于找到从点A到Z的最短路径。但是在这种情况下，并且参照所提及的规则，起点和终点之间的所有节点都必须是路径的一部分。 – lightworks

您提供的链接是使用MST的TSP的2近似值。这很有趣，但我认为它不像书面回答这个问题。如果你提到它是答案中的近似值，它也会更好。 –

这个答案的第一部分看起来不太好。让我们先看看条件：有开始，结束节点和所有节点必须遍历。现在使用Prims算法，您可以得到一棵具有最低边缘成本的树，并且您必须得到一棵线性树，起始和结束节点是树叶。使用TSP是这里的解决方案 –

中的最短路径算法 - 与已知的开始和结束

回答

相关问题