我正在嘗試使用 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() ..），但是不確定如何實施。我嘗試了很多放松的變體，但到目前為止沒有一個接近正確答案。謝謝！