Кратчайший путь между столицами, проходящий через другие столицы

Я пытаюсь разработать код для работы в колледже, и у меня есть алгоритм, который дает мне кратчайший путь между двумя узлами в графе. Обратите внимание, что узлы - это страны, у которых есть столица.

Может ли кто-нибудь объяснить мне, как я могу разработать что-то, что дает мне кратчайший путь из страны 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;
}

Спасибо.


java nodes path shortest-path
person Rafael Moreira    schedule 07.11.2019    source источник
comment
Какое исследование проблемы вы проводили перед тем, как начать писать код?   -  person ct_    schedule 07.11.2019
comment
@ct_ У меня есть задание в колледже, в котором мне предлагается создать график со странами и границами, а затем разработать этот алгоритм. Они также дали мне алгоритм, который дает мне наиболее удобный путь и расстояние между точкой A и точкой B.   -  person Rafael Moreira    schedule 07.11.2019
comment
Учитывая эту информацию, какое исследование вы впоследствии провели?   -  person ct_    schedule 07.11.2019
comment
Я обнаружил нечто, называемое алгоритмом Флойд Варшалла, но с этим периодом времени я не могу разработать матрицу и реализовать этот алгоритм, потому что у меня уже есть вещи, работающие с графиками.   -  person Rafael Moreira    schedule 07.11.2019

Ответы (1)


arrow_upward
1
arrow_downward

описание проблемы:

Дан граф с вершинами V и ребрами E. Мы хотим найти путь P между Va и Vb такой, что:

  • путь содержит {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
person Joris Schellekens    schedule 07.11.2019
comment
Большое тебе спасибо. Не могли бы вы объяснить мне, что вы имеете в виду, говоря, что verticesToBeVisited содержит Vn, и что означает continue? - person Rafael Moreira; 07.11.2019
comment
Под словом «содержащийся» я подразумеваю прошедшее время слова «содержит». Это означает, что вам нужно сохранить, содержит ли verticesToBeVisited Vn, и использовать эту логическую переменную позже. Продолжить - актуальное ключевое слово на большинстве языков. Это означает «пропустить эту итерацию цикла». - person Joris Schellekens; 12.11.2019