我正在尝试使用 Bellman-Ford 算法在图中找到最佳路径。但是，我不希望使用所有边的总和来计算路径长度，而是希望伤亡最少的路径。我们使用以下公式计算伤亡人数：remainingSoldiers = sqrt(a^2 - b^2)，其中 A 是我军，B 是敌军，remainingSoldiers 是战斗结束后我方士兵的数量。
举个例子：假设我们要征服城市 D。我们从顶点 A 开始，部队人数为 100。我们的军队行进到顶点 B，那里有一支人数为 50 的敌军巡逻。根据我们的公式，我们有 86士兵离开了。接下来我军前往顶点C，所以我们86名士兵与40名巡逻顶点C的士兵战斗，我们还剩下76名士兵。最后，我们的 76 名士兵前往由 70 名敌方士兵守卫的顶点 D。根据我们的公式，我们用 29 名士兵征服了顶点 D。
所以为了找到最佳路径，我们必须计算走哪条路径才能使伤亡最少。我得到的提示是将我军的力量和敌军的力量设置为边的权重，并使用带有改进松弛算法的Bellman-Ford来找到最佳查找路径。这正是我在下面的代码中所做的。
我意识到，为了找到最佳路径，我必须找到伤亡人数最少的路径，而不是剩余士兵人数最多的路径，因为找到人数最多的路径是一个 NP 完全问题。
我的代码如下（我正在为图形使用自定义库，但它应该非常简单易懂）：
public Map<Vertex, Double> bellmanFord(Vertex s) {
Map<Vertex, Double> d = g.createVertexMap(Double.POSITIVE_INFINITY);
d.put(s, 0d);
for (int i = 0; i < g.getVertices().size(); i++)
for (Edge e : g.getEdges())
relax(e, d);
return d;
}
public void relax(Edge e, Map<Vertex, Double> d) {
Vertex u = e.getSource();
Vertex v = e.getTarget();
if (d.get(u) + e.getWeight() < d.get(v))
d.put(v, d.get(u) + e.getWeight());
}
下面是我为放松而修改的代码：
public void relax(Edge e, Map<Vertex, Double> d) {
Vertex u = e.getSource();
Vertex v = e.getTarget();
if (d.get(u) - formula(g.getEdge(u, v).getWeight(), g.getEdge(v, u).getWeight()) > d.get(v))
d.put(v, d.get(u) - formula(g.getEdge(u, v).getWeight(), g.getEdge(v, u).getWeight()));
}
但是，我的代码输出的完全是胡说八道。你能帮我解决我的问题并在 Bellman-Ford 算法的松弛方法中实现公式吗？
这是我启动代码时使用的图表（不是边缘情况，只是用于测试基本功能的随机图表）：https://i.imgur.com/Y2OhfDj.png。我们试图从A市攻克H市，我们120人的军队位于A市。当运行我修改后的代码时，bellman-ford 输出以下内容：{a=Infinity, d=Infinity, f=Infinity, g=Infinity, b=Infinity, c=Infinity, h=Infinity, e=Infinity}.我想我必须以某种方式修改代表我的军队力量的边，因为我的算法（我可以在任何边上使用方法 .setWeight() ..），但是不确定如何实施。我尝试了很多放松的变体，但到目前为止没有一个接近正确答案。
谢谢！
Smart猫小萌
相关分类