问求图中约束最短路径的有效数据结构

EN

图G=(V,E)中的约束最短路径问题是:给定源节点s和接收节点t，求出从s到t的最短路径，使得路径上的总资源消耗最多是标量R。图中的每个弧(i,j)都有一个代价，即标量c_{ij}，并以标量r_{ij}的方式消耗资源。路径的成本是构成路径的单个弧的成本之和，路径所消耗的资源是构成路径的各个弧的资源之和。众所周知，这个问题是NP-HARD问题。

解决这个问题的大多数实现都使用了动态规划方法，这种方法本质上是一种蛮力枚举，以及其他聪明的、深入浅出的方法，以减少搜索量。

动态规划是使用标签法实现的。

我使用了几种不同的方法实现了这个算法，我想确保我是否在尽可能高效地执行这个算法。

标记方法创建多个标签，这些标签本质上是从s到其他各个节点的部分路径。在算法过程中会创建大量标签(注意，问题是NP HARD)，直到满足停止条件为止。

每个标签可以表示为一个struct，如下所示。

struct labels_s {
    double current_states[10];
    double unscanned_states[10];
    int already_visited[100];//If node i is already visited on partial path, already_visited[i] = 1, else 0
    int do_not_visit[100];//if node i is not to be visited from this label, do_not_visit[i] = 1; 0 otherwise
    struct labels_s* prev;
    struct labels_s* next;
};

随着算法的进行，需要创建和存储上述许多结构。

方法1:

我很早就实现了这一点，在计算上效率很低。这涉及到在需要新标签时使用new结构，并使用struct的成员、next和prev显式地维护链接列表中的结构。

方法2:

我不再使用newing structs，而是开始将新的结构存储在std::vector容器中：

vector <labels_s> labels;

要做到这一点，而且由于vector提供了对各种标签的整数索引访问，prev和next of struct labels_s可以更改为int prev;和int next;。

存储标签涉及以下内容：

struct labels_s newlabel;//Step 1
//populate newlabel's members//Step 2
labels.push_back(newlabel);//Step 3

使用方法2对同一问题的计算次数明显优于方法1。标签只在向量的末尾添加。没有必要在向量中间插入或从向量中删除。

除了方法2之外，还有其他方法来管理这些标签吗？

我主要关注的是方法2的步骤3。既然push_back()创建了一个newlabel的副本，那么这个复制操作是否很昂贵，可以避免吗？

我正在考虑的另一种方法是维护指向标签结构的指针向量，而不是像我目前这样做的标签结构向量。但在我看来，维护指向标签结构的指针向量不应该比方法1更有效。

如有任何意见，我们将不胜感激。