我正在嘗試使用 Bellman-Ford 算法在圖中找到最佳路徑。但是，我不希望使用所有邊的總和來計(jì)算路徑長(zhǎng)度，而是希望傷亡最少的路徑。我們使用以下公式計(jì)算傷亡人數(shù)：remainingSoldiers = sqrt(a^2 - b^2)，其中 A 是我軍，B 是敵軍，remainingSoldiers 是戰(zhàn)斗結(jié)束后我方士兵的數(shù)量。舉個(gè)例子：假設(shè)我們要征服城市 D。我們從頂點(diǎn) A 開始，部隊(duì)人數(shù)為 100。我們的軍隊(duì)行進(jìn)到頂點(diǎn) B，那里有一支人數(shù)為 50 的敵軍巡邏。根據(jù)我們的公式，我們有 86士兵離開了。接下來我軍前往頂點(diǎn)C，所以我們86名士兵與40名巡邏頂點(diǎn)C的士兵戰(zhàn)斗，我們還剩下76名士兵。最后，我們的 76 名士兵前往由 70 名敵方士兵守衛(wèi)的頂點(diǎn) D。根據(jù)我們的公式，我們用 29 名士兵征服了頂點(diǎn) D。所以為了找到最佳路徑，我們必須計(jì)算走哪條路徑才能使傷亡最少。我得到的提示是將我軍的力量和敵軍的力量設(shè)置為邊的權(quán)重，并使用帶有改進(jìn)松弛算法的Bellman-Ford來找到最佳查找路徑。這正是我在下面的代碼中所做的。我意識(shí)到，為了找到最佳路徑，我必須找到傷亡人數(shù)最少的路徑，而不是剩余士兵人數(shù)最多的路徑，因?yàn)檎业饺藬?shù)最多的路徑是一個(gè) NP 完全問題。我的代碼如下（我正在為圖形使用自定義庫(kù)，但它應(yīng)該非常簡(jiǎn)單易懂）：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 算法的松弛方法中實(shí)現(xiàn)公式嗎？這是我啟動(dòng)代碼時(shí)使用的圖表（不是邊緣情況，只是用于測(cè)試基本功能的隨機(jī)圖表）：https://i.imgur.com/Y2OhfDj.png。我們?cè)噲D從A市攻克H市，我們120人的軍隊(duì)位于A市。當(dāng)運(yùn)行我修改后的代碼時(shí)，bellman-ford 輸出以下內(nèi)容：{a=Infinity, d=Infinity, f=Infinity, g=Infinity, b=Infinity, c=Infinity, h=Infinity, e=Infinity}.我想我必須以某種方式修改代表我的軍隊(duì)力量的邊，因?yàn)槲业乃惴ǎㄎ铱梢栽谌魏芜吷鲜褂梅椒?.setWeight() ..），但是不確定如何實(shí)施。我嘗試了很多放松的變體，但到目前為止沒有一個(gè)接近正確答案。謝謝！