Shortest Path between capitals passing through other capitals

Question

I am trying to develop some code for a college work and I have an algorithm that gives me the shortest path between two nodes in a graph. Please note that the nodes are Countries that have a capital.

Can anyone explain me how I can develop something that gives me the shortest path from country A to country B passing trough a list of capitals (countries)?

I have implemented a method that gives me the distance between two geographical points as well.

My initial thought was to order the list of capitals based on their distance to the country A and then sum all the distances of the shortest path between country A and the first of the list, then the first of the list and the third of the list and so on. Apparentely this is not correct.

    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;
}

Thank you.

Answer 1

problem description:

Given a graph with vertices V and edges E. We want to find a path P between Va and Vb such that:

• the path contains {V0, V1, ..} (some subset of V)
• the sum of weights on edges in P is minimal

pseudo-code:

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