The longest path in the increase chart

Question

Sorry if these are very simple questions for some of you, but I'm new to C ++ (not to mention the Boost Graph Library) and could not understand this problem. So far, I have been able to formulate / assemble the code for creating the graph using the code below.

Now I am trying to calculate the code to find the longest path in this graph.

Can someone help with what will happen to the code? I am having trouble trying to figure out if / how to go through each node and / or edge when trying to find a path?

I should try to get all the nodes and edges back in the longest way.

Any help would be greatly appreciated.

PS 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; // ... 

Answer 1

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

To find the longest path you need to just invert the weight (W), use either Constant-W or 1 / W. If the constant is 0, then this means its negation (-W).

Answer 2

I agree that you need to be careful about canceling the mark. Firstly, the shortest path algorithms are intended only for positive gradients. You have some options (for example, the Bellman-Ford algorithm) that generalize to graphs with negative weight, they do not guarantee the return of the optimal answer if there are negative cycles on the graph.