4
Извините, если это очень простые вопросы для некоторых из вас, но я новичок в C++ (не говоря уже о Boost Graph Library) и не мог понять эту проблему. До сих пор мне удалось сформулировать/собрать код для создания графика, используя приведенный ниже код.Самый длинный путь в диаграмме Boost
Теперь я пытаюсь выяснить код, чтобы найти самый длинный путь на этом графике.
Может кто-нибудь, пожалуйста, помогите с кодом? У меня возникли проблемы с попыткой выяснить, если/как пройти через каждый узел и/или край при попытке найти путь?
Я должен попытаться вернуть все узлы и ребра в самый длинный путь.
Любая помощь будет принята с благодарностью.
P.S. кто-нибудь знает, если C++ организовал документацию, такую как Javadoc ??
#include <boost/graph/dag_shortest_paths.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <windows.h>
#include <iostream>
int main()
{
using namespace boost;
typedef adjacency_list<vecS, vecS, directedS, property<vertex_distance_t, double>, property<edge_weight_t, double> > graph_t;
graph_t g(6);
enum verts { stationA, stationB, stationC, stationD, stationE, stationF };
char name[] = "rstuvx";
add_edge(stationA, stationB, 5000.23, g);
add_edge(stationA, stationC, 3001, g);
add_edge(stationA, stationD, 2098.67, g);
add_edge(stationA, stationE, 3298.84, g);
add_edge(stationB, stationF, 2145, g);
add_edge(stationC, stationF, 4290, g);
add_edge(stationD, stationF, 2672.78, g);
add_edge(stationE, stationF, 11143.876, g);
add_edge(stationA, stationF, 1, g);
//Display all the vertices
typedef property_map<graph_t, vertex_index_t>::type IndexMap;
IndexMap index = get(vertex_index, g);
std::cout << "vertices(g) = ";
typedef graph_traits<graph_t>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = vertices(g); vp.first != vp.second; ++vp.first)
std::cout << index[*vp.first] << " ";
std::cout << std::endl;
// ...
// Display all the edges
// ...
std::cout << "edges(g) = " << std::endl;
graph_traits<graph_t>::edge_iterator ei, ei_end;
for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
std::cout << "(" << index[source(*ei, g)] << "," << index[target(*ei, g)] << ") \n";
std::cout << std::endl;
// ...
Прежде всего, спасибо за ваш ответ. Я посмотрел на этот пример. Как я уже сказал, я новичок в C++, я надеялся увидеть код, как я могу пройти через весь график? Кроме того, Dijkstra может работать над этим простым базовым графиком. Но в целом для более длинных/больших графиков отрицание весов может быть не решением, особенно если оно не ациклично. – TheTSPSolver
Проверьте это для обхода графа: http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/depth_first_search.html http://www.boost.org/doc/libs/ 1_43_0/libs/graph/example/dfs-example.cpp Я думаю, что Dijkstra также будет работать на больших графиках (не могли бы вы указать причину?). И если графики являются циклическими, конечно, самый длинный путь будет бесконечным. – monn
Ну, из того, что я знаю, мы не можем использовать отрицательные веса с Дийкстра. Однако, подумайте об этом, 1/| W | может работать (учитывая, что все весовые коэффициенты имеют положительные значения). Большое спасибо. для вашей обратной связи. – TheTSPSolver