寻找最短路径

我有50节点或更多的经度和纬度。它没有互相连接。我们会将一个节点视为开始和结束两个节点。寻找最短路径

我需要找到从'start'开始的这些节点的最短路径，结束于同一个开始点并通过所有节点。

注：没有使用谷歌地图API

来源

2014-04-23 Ravi Mishra

请问点之间的大概距离是否足够呢？明确给出每对节点的距离？ – Codor

你能否介绍一下这个问题？该图是否定向？如果是这样，最短路径不能通过所有的节点。 – Dany

@DineshAppavoo它既没有连接也没有指示。我需要获得最短路径的解决方案。 –

您所描述的问题是Euclidean TSP，这是NP难问题。

对于非常小的输入，你可以使用蛮力来做到这一点。对于较大的输入，可以使用近似算法（例如链接中提到的保证2逼近的算法）。

来源

2014-04-23 07:59:12

您能否在这里粘贴一些代码以供参考？因为我正在使用TSP，但没有给出准确的结果。我需要找到节点的左/右子节点，以便它将连接图并在此基础上获得结果。 –

但是你没有样本数据在这里，我想这可能工作：

names<-#read your nodes 
rest<-list() 
A<-list() 
n=1 
for (i in 1:50){ 
    A<-get.all.shortest.paths(aracne_graph, names[i], names[i], mode = c("all"), weights=NULL) 
    rest[[n]]<-A$res 
    n<-n+1 
    } 
}

来源

2014-05-03 11:21:42 Sadegh

请详细说明一下吗？ –

是的，名称文件包含所有节点。然后你有一个图表（例如这里ARACNE_graph）。因此，您想要搜索文件名中节点到同一节点的最短路径（名称[i]，名称[i]）。 – Sadegh

我详细了解您的想法！ –

寻找最短路径

回答

相关问题