Longest Path in Boost Graph

Sorry if this is a very basic questions for some of you but I'm new to C++ (let alone Boost Graph Library) and couldn't figure out this problem. So far I've been able to formulate/gather开发者_开发知识库 code to create a graph using the code below.

Now I'm trying to figure out the code to find the longest path in this graph.

Can someone please help with what would the code be? I was having trouble trying to figure out if/how to traverse through each node and/or edge when trying to find the path?

I have to try to return all the nodes and edges in the longest path.

Any help will be greatly appreciated.

P.S. does anyone know if C++ has organized documentation like 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;
    // ...

---

I think you should check the example in your boost distribution. Online : http://www.boost.org/doc/libs/1_38_0/libs/graph/example/dijkstra-example.cpp

To make it find the longest path you need to simply inverse the weight (W), either use a Constant - W, or 1/W. If the constant is 0, then it means it's a negation (-W).

---

I agree that one has to be careful about sign reversal. Firstly, most shortest path algorithms are only for positive edge graphs. You do have some options (e.g Bellman-Ford algorithm) that generalize to graphs with negative weight, they are not guaranteed to return the optimal answer if there are negative cycles in the graph.