通过其他首都的首都之间的最短路径
Shortest Path between capitals passing through other capitals
我正在尝试为一项大学作业开发一些代码,并且我有一个算法可以为我提供图中两个节点之间的最短路径。请注意,节点是拥有首都的国家。
任何人都可以向我解释我如何开发一些东西,让我通过首都(国家)列表从国家 A 到国家 B 的最短路径?
我已经实现了一种方法,它也可以给出两个地理点之间的距离。
我最初的想法是根据首都到A国的距离对列表进行排序,然后将A国与列表第一个之间的最短路径的所有距离相加,然后是列表第一个和列表的第三个等等。显然这是不正确的。
public double shortestPathCapitals2(List<String> capitais, Pais pOrig, Pais pDest) {
double dist = 0;
LinkedList<Pais> shortPath = new LinkedList<Pais>();
LinkedList<String> temp = new LinkedList<>(capitais);
temp.addFirst(pOrig.getCapital());
temp.addLast(pDest.getCapital());
Collections.sort(temp, (c1, c2) -> (int) (distance(pOrig, shortestPathCapitals2(c2)) - distance(pOrig, obterPaisPorCapital(c1))));
for (int i = 0; i < temp.size() - 1; i++) {
Pais p1 = obterPaisPorCapital(temp.get(i));
Pais p2 = obterPaisPorCapital(temp.get(i + 1));
dist += shortestPath(p1, p2, shortPath);
shortPath.clear();
}
return dist;
}
谢谢。
问题描述:
给定一个顶点为 V、边为 E 的图。
我们想在 Va 和 Vb 之间找到一条路径 P,使得:
- 路径包含 {V0, V1, ..}(V 的某个子集)
- 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, endVertex, verticesToBeVisited, currentPath)
// clean up
if verticesToBeVisited contained Vn:
verticesToBeVisited += Vn
currentPath -= Vn
我正在尝试为一项大学作业开发一些代码,并且我有一个算法可以为我提供图中两个节点之间的最短路径。请注意,节点是拥有首都的国家。
任何人都可以向我解释我如何开发一些东西,让我通过首都(国家)列表从国家 A 到国家 B 的最短路径?
我已经实现了一种方法,它也可以给出两个地理点之间的距离。
我最初的想法是根据首都到A国的距离对列表进行排序,然后将A国与列表第一个之间的最短路径的所有距离相加,然后是列表第一个和列表的第三个等等。显然这是不正确的。
public double shortestPathCapitals2(List<String> capitais, Pais pOrig, Pais pDest) {
double dist = 0;
LinkedList<Pais> shortPath = new LinkedList<Pais>();
LinkedList<String> temp = new LinkedList<>(capitais);
temp.addFirst(pOrig.getCapital());
temp.addLast(pDest.getCapital());
Collections.sort(temp, (c1, c2) -> (int) (distance(pOrig, shortestPathCapitals2(c2)) - distance(pOrig, obterPaisPorCapital(c1))));
for (int i = 0; i < temp.size() - 1; i++) {
Pais p1 = obterPaisPorCapital(temp.get(i));
Pais p2 = obterPaisPorCapital(temp.get(i + 1));
dist += shortestPath(p1, p2, shortPath);
shortPath.clear();
}
return dist;
}
谢谢。
问题描述:
给定一个顶点为 V、边为 E 的图。 我们想在 Va 和 Vb 之间找到一条路径 P,使得:
- 路径包含 {V0, V1, ..}(V 的某个子集)
- 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, endVertex, verticesToBeVisited, currentPath)
// clean up
if verticesToBeVisited contained Vn:
verticesToBeVisited += Vn
currentPath -= Vn