假設我有一個G帶有N頂點和M邊的圖。每條邊都有它的長度和時間（假設以分鐘為單位），它需要遍歷該邊。我需要找到圖中頂點1和之間的最短路徑，該路徑在幾分鐘內N執行T。由于時間是更有價值的資源，我們關心及時遍歷圖，并且只有在最小長度的情況下，我決定使用 Dijkstra 演算法，為此我將每條邊的時間視為其權重。我添加了一個向量來存盤持續時間。因此，該演算法回傳最少的時間，而不是最少的長度。一位朋友建議在我的代碼中添加以下內容：
int answer(int T) {
int l = 1;
int r = M; // a very big number
int answer = M;
while (l <= r) {
int mid = (l r) / 2;
int time = dijkstra(mid); // the parameter mid serves as an upper bound for dijkstra and I relax the edge only if its length(not time) is less than mid
if (time <= T) {
answer = mid;
r = mid - 1;
} else {
l = mid 1;
}
}
if (best == M) {
return -1; // what we return in case there is no path in the graph, which takes less than T minutes
}
return answer;
}
這是dijkstra方法（Graph帶有的類的一部分std::unordered_map<int, std::vector<Node>> adjacencyList member）：
int dijkstra(int maxLength) {
std::priority_queue<Node, std::vector<Node>, NodeComparator> heap;//NodeComparator sorts by time of edge
std::vector<int> durations(this->numberOfVertices 1, M);
std::set<int> visited;
// duration 1->1 is 0
durations[1] = 0;
heap.emplace(1, 0, 0);
while (!heap.empty()) {
int vertex = heap.top().endVertex;
heap.pop();
// to avoid repetition
if (visited.find(vertex) != visited.end()) {
continue;
}
for (Node node: adjacencyList[vertex]) {
// relaxation
if (node.length <= maxLength && durations[node.endVertex] > durations[vertex] node.time) {
durations[node.endVertex] = durations[vertex] node.time;
heap.emplace(node.endVertex, durations[node.endVertex], 0);
}
}
// mark as visited to avoid going through the same vertex again
visited.insert(vertex);
}
// return path time between 1 and N bounded by maxKilograms
return durations.back();
}
這似乎有效，但對我來說似乎效率低下。老實說，我完全不理解他的想法。在我看來，就像隨機嘗試找到最佳答案一樣（因為沒有人說邊的時間與其長度成正比）。我嘗試搜索，shortest path in graph with time limit但我發現演算法可以找到最快的路徑，而不是有限制的最短路徑。甚至存在這樣的演算法嗎？如何改進我的解決方案？
uj5u.com熱心網友回復：
這是什么？
int time = dijkstra(mid);
它當然不是 Dijkstra 演算法的實作！
Dijkstra 演算法需要起始節點并回傳從起始節點到其他節點的最短路徑。
您將需要一個函式來回傳開始節點和結束節點之間占用時間小于 T 的所有不同路徑。然后您可以搜索它們中最便宜的路徑。
Search graph for all distinct paths from start to end
Discard paths that take more then T
Select cheapest path.
uj5u.com熱心網友回復：
尋找資源受限的最短路徑是 NPHard。解決這個問題的大多數方法都采用標記方案，這是動態規劃的一種特殊化。您可以使用可用的庫來完成此操作。請參閱此處了解提升實施。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/388164.html