Блог

В настоящее время я изучаю библиотеки JGraphT для управления графами на Java, в частности, я пытаюсь определить самый длинный путь между 2 узлами в простом графике, и я знаю, что могу добраться туда с помощью рекурсивного метода. В любом случае, я нашел в Java docs библиотеку AllDirectedGraphs, которая может справиться с этой задачей в случае ориентированных графиков, вот простой пример:

 
//the nodes of the graph are countries and the edges are the routes that connect the countries by land

AllDirectedPaths<Country, DefaultEdge> paths = new AllDirectedPaths<Country, DefaultEdge(graph);

//getting all the paths between 2 random countries
         
List<GraphPath<Country, DefaultEdge>> longestPath = paths.getAllPaths(countries.get(220), countries.get(325), true, null);

GraphPath<Country, DefaultEdge> obj = null;
double maxlenght=0;
         
for( GraphPath<Country, DefaultEdge> pa :longestPath ) {
                     
         if(pa.getLength()>maxlenght)
             obj= pa;
        }
return obj;
}
 

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