我正在尝试为大学工作开发一些代码,并且我拥有一种算法,该算法为我提供了图中两个节点之间的最短路径。请注意,这些节点是拥有资本的国家/地区。
有人能解释我如何开发出一条使我从A国到B国的最短路径经过一系列首都(国家)的东西吗?
我已经实现了一种方法,该方法也可以使我知道两个地理位置之间的距离。
我最初的想法是根据首都到国家A的距离排序列表,然后将国家A与列表中第一个之间的最短路径的所有距离相加,然后列出列表中的第一个和第三个列表等等。显然这是不正确的。
@Provides
谢谢。
我正在尝试为大学工作开发一些代码,并且我拥有一种算法,该算法为我提供了图中两个节点之间的最短路径。请注意,这些节点是拥有资本的国家/地区。
有人能解释我如何开发出一条使我从A国到B国的最短路径经过一系列首都(国家)的东西吗?
我已经实现了一种方法,该方法也可以使我知道两个地理位置之间的距离。
我最初的想法是根据首都到国家A的距离排序列表,然后将国家A与列表中第一个之间的最短路径的所有距离相加,然后列出列表中的第一个和第三个列表等等。显然这是不正确的。
@Provides
谢谢。
问题描述:
给出一个具有顶点V和边E的图。 我们想要找到Va和Vb之间的路径P,这样:
伪代码:
function findPath(startVertex,endVertex,verticesToBeVisited,currentPath)
// check if we have reached the destination
if startVertex == endVertex:
/*
* there are multiple ways of reaching the destination
* calculate the length of the past (also called the cost)
* if the cost is lower than the current minimum,store the path
*/
cost = calculateCost(currentPath)
if cost < currentMinCost:
currentMinCost = cost
currentMinPath = currentPath
else:
/*
* if we have not reached the destination
* we need to try all possible next hops
* this algorithm uses recursion to do so
*/
for every vertex Vn that is a neighbour of startVertex:
/*
* this check prevents us from going
* Paris --> Rome --> Paris --> Rome (endlessly)
*/
if currentPath contains Vn:
continue
// add the next hop to our path
currentPath += Vn
// if this vertex needed to be visit,cross it out in the list
if verticesToBeVisited contains Vn:
verticesToBeVisited -= Vn
// recursion
findPath(Vn,currentPath)
// clean up
if verticesToBeVisited contained Vn:
verticesToBeVisited += Vn
currentPath -= Vn