JGraphT - поиск пути с помощью BreadthFirstIterator

Вот код для обхода графика с BreathFirstIterator:

public class GraphTest {

    public static void main(String[] args) {
        DirectedGraph<Integer, DefaultEdge> graph = 
            new DefaultDirectedGraph <Integer, DefaultEdge>(DefaultEdge.class);

        graph.addVertex(7);
        graph.addVertex(4);
        graph.addVertex(9);
        graph.addVertex(3);
        graph.addVertex(2);
        graph.addVertex(5);


        graph.addEdge(7, 4);
        graph.addEdge(7, 9);
        graph.addEdge(9, 3);
        graph.addEdge(3, 2);
        graph.addEdge(3, 5);

        GraphIterator<Integer, DefaultEdge> iterator = 
                new BreadthFirstIterator<Integer, DefaultEdge>(graph);
        while (iterator.hasNext()) {
            System.out.println( iterator.next() );
        }
    }
}

Как и ожидалось, код распечатывает список всех посещенных вершин: 7,4,9,3,2,5. Моя проблема в том, что я не знаю, как я могу использовать этот API для получения пути с удаленными откатами алгоритма. Например, для пути от 7 до 2 будет выведено 7->9->3->2, а не только список посещенных вершин. Остановить его после достижения пункта назначения явно недостаточно. Кто-нибудь уже решил эту проблему?


java graph jgrapht
person TheMP    schedule 04.10.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Можно получить кратчайший путь между двумя вершинами с помощью _ 1_. Он обеспечивает реализацию алгоритма кратчайшего пути Дейкстры с использованием ClosestFirstIterator. Если такого пути нет, он вернет null.

Образец кода:

DirectedGraph<Integer, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class);

graph.addVertex(7);
graph.addVertex(4);
graph.addVertex(9);
graph.addVertex(3);
graph.addVertex(2);
graph.addVertex(5);

graph.addEdge(7, 4);
graph.addEdge(7, 9);
graph.addEdge(9, 3);
graph.addEdge(3, 2);
graph.addEdge(3, 5);

List<DefaultEdge> path = DijkstraShortestPath.findPathBetween(graph, 7, 2);
System.out.println(path); // prints [(7 : 9), (9 : 3), (3 : 2)]
person Tunaki    schedule 04.10.2015
comment
У меня уже есть решение для поиска кратчайшего пути с помощью алгоритма Дейкстры, но в этом случае мне не нужен кратчайший путь - мне нужен ЛЮБОЙ путь, который можно найти с помощью BFS (возможно, с наименьшим количеством переходов). - person TheMP; 04.10.2015
comment
@Niemand Ну, путь с наименьшим количеством скачков - это кратчайший путь, найденный алгоритмом Дейкстры. Так вы хотите их все или только самый короткий? - person Tunaki; 04.10.2015
comment
В этом упрощенном случае, о котором идет речь, да, можно использовать Dijkstra. Но в моем реальном примере у меня есть взвешенное ребро, и я хочу найти путь специально с помощью поиска в ширину и игнорировать веса, минимизируя количество передач между узлами. Итак, в заключение - я хочу иметь алгоритм, который находит один единственный путь с наименьшим количеством передач независимо от веса ребра. BFS показался мне хорошим выбором. - person TheMP; 04.10.2015
comment
@Niemand Это полностью вопрос, отличный от того, который вы задали. Это совсем не связано с DirectedGraph, но с WeightedGraph, что совсем другое. Вы вообще не упоминаете веса в своем вопросе. - person Tunaki; 04.10.2015
comment
Может я слишком упростил свой случай :) Попробую исправить сейчас - person TheMP; 04.10.2015
comment
@Niemand Пожалуйста, не редактируйте свой пост, так как вы сильно измените заданный вами вопрос. Я предлагаю вам создать еще один вопрос, более конкретный для вашего варианта использования. Это может быть полезно для будущих посетителей, желающих получить пример алгоритма Дейкстры. - person Tunaki; 04.10.2015
comment
Хорошо, я оставлю все как есть. Сюда перемещен новый вопрос - stackoverflow.com/questions/32935692 / - person TheMP; 04.10.2015