我有一个带权重的图,没有负权重,并且我想找到从一个节点到另一个节点的路径,尝试最小化单步的成本。我不需要最小化行程的总成本(例如Dijkstra算法),但需要最小化平均步骤成本。然而,我有一个限制:K,路径中节点的最大数量。
例如,要从A到J,Dijkstra可能会找到这条路径(括号内是权重):
A (4) D (6) J -> total cost: 10
我需要的算法,设置 K = 10,会找到类似以下的结果:
A (1) B (2) C (2) D (1) E (3) F (2) G (1) H (3) J -> total cost: 15
这个问题是否有已知的算法?感谢您的提前回复。
Eugenio
作为对templatetypedef答案的编辑。
一些问题:
1)实际上,为了降低平均值,可能需要多次遍历同一个环路,这对我的问题来说不太好:也许我应该提到它,但我不想重复访问同一个节点。
2)我是否可以利用没有负权值的事实?
3)当您说O(kE)时,是指整个算法还是仅指附加部分?
让我们看看在C语言中的这个简单实现,其中n表示节点数,e表示边数,d是距离向量,p是前任向量,结构边(u,v,w)将边缘存储在图形中。
for (i = 0; i < n; ++i)
d[i] = INFINITY;
d[s] = 0;
for (i = 0; i < n - 1; ++i)
for (j = 0; j < e; ++j)
if (d[edges[j].u] + edges[j].w < d[edges[j].v]){
d[edges[j].v] = d[edges[j].u] + edges[j].w;
p[edges[j].v] = u;
}
我不确定我应该如何根据你的回答修改代码;如果考虑平均成本而不是总成本,这样就足够了吗?
for (i = 0; i < n; ++i)
d[i] = INFINITY;
d[s] = 0;
for (i = 0; i < n - 1; ++i)
steps = 0;
for (j = 0; j < e; ++j)
if ( (d[edges[j].u]+ edges[j].w)/(steps+1) < d[edges[j].v]/steps){
d[edges[j].v] = d[edges[j].u] + edges[j].w;
p[edges[j].v] = u;
steps++;
}
但是,我不知道如何同时考虑K限制...再次感谢您的帮助。
编辑 由于我可以容忍一些错误,所以我正在考虑这种天真的解决方案:
- 预先计算所有最短路径并在A中存储
- 在修改后的图上预先计算所有最短路径,在某个权重上切断边缘,并在B中记忆它们
当我需要一条路径时,首先查找A中的路径,例如从x到y的路径是 x->z->y 然后对于每一步,我在B中查找, 因此对于x > z,我查看B中是否存在连接,如果不存在,则保留x > z,否则我使用B提供的子路径填充x > z路径,可能类似于x->j->h->z; 然后我对z->y执行相同的操作。 每次我还将检查是否添加了循环路径。
也许我会得到一些奇怪的路径,但在大多数情况下,它可能有效。 如果我尝试使用不同的"截断阈值"扩展解决方案,也许我也可以接近满足K约束。