CODEWITHSUNDEEP
c++graphshortest-path
superDoge
superDoge

Reputation: 71

How can I store the data for multiple objective in shortest path search in C++

I'm now working on the shortest path search in a graph with N nodes, and its edges have not only length but also other costs. In total, I have to consider four to seven costs for an edge. In the classical shortest path search written in C++, I use an array int* with size of N to store the cost at each node. But this does not work with this multiple objective graph as I need to store many intermedia data for each node because there are many objectives and it is not possible to decide which one is the best when the new edge is taken into consideration.

example for costs

For example, under this image. If I only consider cost in black, then it would be easy to say the cost is 3 from node 1 to node 2. If I consider both red and black costs, at node 2 I have to store (3,7) and (6,5) for the further search. In this case, for each node, the stored data is not at a fixed size, so int* does not work. Maybe I should use vector to store the data for each node, but as I Googled, people say it's not a good idea to use array of vector to store the data. Then I thought vector<vector<pairs <int, int>>> is a possible solution, would it be too large if the graph is so big. If not so, would it be kind of waste computation because updates for data of each nodes are frequent during the search. I wonder if there is a better way to store data during this process? Thanks in advance.

Upvotes: 0

Views: 129

Answers (1)

ravenspoint
ravenspoint

Reputation: 20492

You already have the edge costs stored somewhere, probably in an edge class. So there is no need to store another copy of the same data.

Store the index of each edge of the path as the path is built, and lookup the costs for each path edge index when required.

Upvotes: 0

Related Questions