我正在尋找一種算法，我肯定已經研究過這個算法，但我對圖理論甚至不熟悉甚至不知道搜索的正確術語。確定最大覆蓋區域的算法
摘要中，我正在尋找一種算法來確定可達頂點[x1，x2，xn]和某個起始頂點之間的路徑集合，當每個邊具有權重並且每個路徑只能有一個給定x的最大總重量。
從更實際的角度來說，我有道路網絡，每條路段都有長度和最大行駛速度。我需要確定從網絡上的任何起點到特定時間範圍內可以達到的區域。如果我能找到在這段時間內可達到的最遠點，那麼我將使用凸包算法來確定面積（這對我的用例來說足夠近似）。
所以我的問題，我如何找到這些終點？我的第一個直覺就是使用Dijkstra的算法，一旦我「消耗」了某個「預算」的時間就停下來，從每條路段的預算中扣除;但是當算法應該回溯但使用其預算時，我會陷入困境。這個問題有沒有一個已知的名字？
如果我正確地理解了這個問題，你的初步猜測是正確的。 Dijkstra算法或任何其他找到從頂點到所有其他頂點（如A *）的最短路徑的算法都適合。
在最簡單的情況下，您可以構建圖形，其中邊的權重表示通過這段路所需的最短時間。如果你有它的長度和最大允許速度，我假設你知道它。從起點運行算法，挑選最短路徑小於x的頂點。就如此容易。
如果你想優化的東西，請注意，在Dijkstra算法的工作中，當前已知的頂點最短路徑隨着每次迭代而單調遞增。當處理具有非負權重的圖時，這是預期的。現在，在每一步中，您將選擇一個具有最小當前最短路徑的未使用頂點。如果此路徑大於x，則可能會停止。從現在開始，您不可能有任何最短路徑小於x的頂點。
如果您需要準確確定頂點之間的點，車輛在給定時間內可以達到的點數，這只是上述算法的一個小擴展。作爲下一步，考慮所有(u, v)邊緣，其中u可以及時到達x，而v不能。即如果我們將頂點w定義爲t(w)的最短路徑，我們有t(u) <= x和t(v) > x。現在使用一些基本的數學運算將u和v之間的點與係數(x - t(u))/(t(v) - t(u))進行內插。
謝謝，這個答案（加上@ div's）讓我走上了正確的道路。當我重新構造問題時，我未能意識到的事情變得很明顯，如下所示：'查找至多*至少從給定起始頂點v1開始的預算x'的所有點。我會讓Dijkstra在整個圖表上運行，而不是在達到給定的終端節點時停止，但是當預算超出時。所有在我的圖形中被訪問的頂點都有一個低於x的預算，然後我的凸包算法會剔除邊界內的所有點。 （cont ...） – Roel
這樣，它甚至可以覆蓋一些病理情況，其中路線中的頂點稍後（如在更接近笛卡爾距離的情況下）更靠近起始節點（因爲道路轉彎繞過障礙物或湖），這將使我的'地區覆蓋'小於所需。這當然正是你說的，但它沒有點擊我，直到我把它寫到我自己的方式上面:) – Roel
從起始節點使用寬度優先搜索似乎是解決O（V + E）時間複雜度問題的好方法。那麼這就是迪克斯特拉所做的，但是在找到最小的路徑後就會停止。但是，對於您的情況，您必須繼續爲您的路線集合收集路線，直到無法延伸路線，並保持其重量小於或等於最大總重量。
而且我不認爲Dijkstra算法中有任何回溯。
謝謝。你是對的，我對回溯的評論是因爲我誤解了我們已經使用的Dijkstra修改版本，對於混淆感到抱歉。 – Roel
您正在查看[最大流量問題]（https://en.wikipedia.org/wiki/Maximum_flow_problem）。你只想要它的名字還是粗略的分析？ – Makoto
查看https://en.wikipedia.org/wiki/Maximum_coverage_problem和相關問題http：// stackoverflow。COM /問題/ 3859891 /算法，用於最大化覆蓋-的矩形區域，具有縮放瓷磚。 – user1929959
@Makoto是嗎？根據我對最大流量的瞭解，只能找到從給定源到給定目的地的一條路徑，並且具有最大「吞吐量」？ – Roel