Возврат только вершин фактического кратчайшего пути

Я знаю, что заголовок немного сумбурный, но я не знаю, как его лучше объяснить.

Что я пытаюсь сделать:

Используя граф, найденный в текстовом файле, найдите и распечатайте кратчайший путь (минимальное количество вершин) из вершины A в вершину B.

Примечание: использование поиска в ширину, а не Дейкстры.

Что у меня есть:

Рабочий алгоритм, применяющий BFS к графу, но не способ распечатать кратчайший путь.

Мне трудно отличить вершину кратчайшего пути от вершины, которая просто проходит через алгоритм, но не в кратчайшем пути.

Например: Найдите кратчайший путь между 0 и 4. 0 соединяется с 1,2 и 3. 1 соединяется с 4. Мой путь оказывается [0,1,2,3,4] вместо [0,1, 4].

Мне не удалось найти темы, задающие тот же вопрос, или какое-либо пошаговое руководство по BFS, включающее этот вопрос, поэтому я не уверен, что делаю это намного сложнее. чем это?

Изменить: код для тех, кому это может быть интересно (вообще не уверен, что я избегаю кругов?)

Изменить 2: изменен способ хранения пути к стеку.

public String findPath(int v, int w) {
    Queue<Integer> q = new LinkedList<Integer>();
    boolean[] visited = new boolean[g.numVertices()];

    q.add(v);
    Stack<Integer> path = new Stack<Integer>();
    while(q.peek() != null) {
        runBFS(q.poll(),w,visited,q,path);
    }
    return path.toString();
} 

private void runBFS(int v, int w, boolean[] visited, Queue<Integer> q, Stack<Integer> path) {
    if(visited[v]) {
    }
    else if(v == w) {
        path.add(v);
        q.clear();
    }
    else {
        path.add(v);
        visited[v] = true;
        VertexIterator vi = g.adjacentVertices(v);
        while(vi.hasNext()) {
                q.add(vi.next());
        }
    }
}

Некоторое объяснение переменных и методов:

v = исходная вершина

w = целевая вершина

г = график

vi = обычный итератор, который выполняет итерацию по соседям v

Спасибо, что прочитали!


java graph-traversal shortest-path breadth-first-search
person bjrnt    schedule 28.03.2011    source источник
comment
Привет, не могли бы вы опубликовать исходный код.   -  person michal.kreuzman    schedule 28.03.2011
comment
Как ваш график представлен в вашем коде? Как избежать кругов? Есть довольно много таких вопросов, на которые лучше всего ответить, опубликовав часть своего кода...   -  person thkala    schedule 28.03.2011
comment
Я добавил немного кода. Если есть какая-либо недостающая информация о графике, дайте мне знать.   -  person bjrnt    schedule 28.03.2011
comment
Я думаю, что мне не хватает нескольких вещей здесь. Во-первых, разве объекты String в Java не являются неизменяемыми? Какая польза от изменения path в runBFS?   -  person thkala    schedule 28.03.2011
comment
Ты абсолютно прав, мой плохой. Однако сейчас я изменил его со String на Stack и внесу соответствующие изменения в код.   -  person bjrnt    schedule 28.03.2011

Ответы (4)


arrow_upward
10
arrow_downward

Вам нужно будет иметь определенное поле пути для каждой вершины. Таким образом, вы можете отслеживать пути, которые вы выбрали, и, следовательно, найденный короткий путь. Я буду использовать массив String, точно так же, как вы использовали логический массив для хранения посещенных вершин.

public String findPath(int v, int w) {
    Queue<Integer> q = new LinkedList<Integer>();
    boolean[] visited = new boolean[g.numVertices()];
    String[] pathTo = new String[g.numVertices()];

    q.add(v);
    pathTo[v] = v+" ";
    while(q.peek() != null) {
        if(runBFS(q.poll(),w,visited,q,pathTo))
        break;
    }
    return pathTo[w];
}

private boolean runBFS(int v, int w, boolean[] visited, Queue<Integer> q, String[] pathTo) {
    if(visited[v]) {
    }
    else if(v == w)
        return true; 
    }
    else {
        visited[v] = true;
        VertexIterator vi = g.adjacentVertices(v);
        while(vi.hasNext()) {
            int nextVertex = vi.next();
            pathTo[nextVertex] = pathTo[v] + nextVertex + " ";
            q.add(nextVertex);
        }
    }
    return false;
}
person jCoder    schedule 28.03.2011
comment
Именно то, что мне было нужно, большое спасибо! Отличное решение, я думаю, моя проблема была в том, что меня интересовал только путь от X до Y и ничего больше. - person bjrnt; 29.03.2011
comment
Потрясающий! Именно то, что я искал. - person Shane Fulmer; 13.06.2011

arrow_upward
6
arrow_downward

Еще одно компактное (с точки зрения пространства) решение, предложенное нашими помощниками и не использующее O(n^2) пространства для хранения, состоит в том, чтобы каждый узел хранил только тот узел, из которого он поступил. Это можно сделать, изменив список посещений на целочисленный массив (int[] visited).

шаг 1: инициализируйте список посещений, чтобы каждый элемент был '-1' или "непосещенным"

шаг 2: пометить первый узел как посещенный сам по себе visited[v] = v;

Сделайте BFS (как и вы, со следующими изменениями:)

при переходе от v -> v_next:

if(visited[v_next] == -1)
{
  visited[v_next] = v;
  q.put(v_next);
}
// else skip it, it's already been visited

Таким образом, если w достижим, Visit[w] сохранит, из какого узла он пришел, из этого узла вы можете вернуться назад к v и, наконец, напечатать их в обратном порядке. (Это делается либо с помощью стека, либо методом рекурсивной печати.)

Надеюсь, это имеет смысл. :)

person pbos    schedule 31.03.2011

arrow_upward
3
arrow_downward

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

Вы можете, например, использовать отдельную очередь, которая будет обрабатываться параллельно, в которой вы будете хранить текущий путь, а затем восстанавливать его, как только вы удалите из очереди следующую вершину для поиска.

person thkala    schedule 28.03.2011
comment
Это полезное объяснение было очень полезным. См. здесь мою реализацию - person c0der; 15.01.2018

arrow_upward
1
arrow_downward

Вам нужно поместить текущий узел в стек и распечатать весь стек только после того, как вы достигнете места назначения.

person regularfry    schedule 28.03.2011
comment
Это вернуло тот же результат, что и мой предыдущий метод, не могли бы вы быть немного подробнее? - person bjrnt; 28.03.2011
comment
Вы вытаскивали его обратно, когда делали резервную копию? - person regularfry; 04.04.2011