我有一個加權無向圖。它的頂點是兩個集合的一部分——S 和 T。首先，輸入邊。然后指定哪些頂點是 T 集的一部分（其余是 S 集的一部分）。然后 q 查詢跟隨。對于每個查詢（由源頂點組成），程式必須列印指定源頂點和集合 T 的任何頂點之間的最短路徑。
我使用 Dijkstra 演算法實作了該程式。我為源頂點上的每個查詢呼叫它（dijkstra 回傳源和所有其他頂點之間的距離），然后回傳這些數字中的最小值。
const int M = 1000000;
std::unordered_set<int> T;
class Node {
public:
int endVertex; // stores the second vertex of the edge
int weight; // stores the weight required, it is the weight of the edge
Node(int end, int weight) {
this->endVertex = end;
this->weight = weight;
}
};
struct NodeComparator {
bool operator()(const Node &first, const Node &second) {
return first.weight > second.weight;
}
};
class Graph {
private:
std::unordered_map<int, std::vector<Node>> adjacencyList; // it's a vector because there may be repeated Nodes
int numberOfVertices;
std::vector<int> dijkstra(int source) {
std::priority_queue<Node, std::vector<Node>, NodeComparator> heap;
std::vector<int> distances(this->numberOfVertices, M);
std::unordered_set<int> visited;
// distance source->source is 0
distances[source] = 0;
heap.emplace(source, 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 (distances[node.endVertex] > distances[vertex] node.weight) {
distances[node.endVertex] = distances[vertex] node.weight;
heap.emplace(node.endVertex, distances[node.endVertex]);
}
}
// mark as visited to avoid going through the same vertex again
visited.insert(vertex);
}
return distances;
}
int answer(int source) {
std::vector<int> distances = this->dijkstra(source);
std::set<int> answer;
for (int i: T) {
answer.insert(distances[i]);
}
return *answer.begin();
}
// other methods
};
// main()
但是，由于超時，我的解決方案沒有通過一半的測驗。我用 Floyd-Warshall 演算法替換了我的 dijkstra 方法，它直接覆寫了起始鄰接矩陣，因為我認為該方法只會被呼叫一次，然后每個查詢只會在矩陣的源行中找到最小元素。這次超時甚至更糟。
是否有針對最短路徑的高效查詢的特定演算法？如何改進我的演算法？
uj5u.com熱心網友回復：
您可以反轉所有邊并找到從 T 集合（從所有 T 頂點一起運行 Dijkstra）到某個頂點 S 的最短路徑。并預先計算到每個 S 的所有距離并在 O(1) 中回答查詢。
uj5u.com熱心網友回復：
這似乎沒有必要
std::unordered_set<int> visited;
法線向量可以更快地完成作業
std::vector<int> visited(numberOfVertices,0);
所以你可以更換
if (visited.find(vertex) != visited.end()) {
隨著更快
if( visited[vertex] )
并且
visited.insert(vertex);
變成
visited[vertex] = 1;
可以加快個別查詢
代替
std::set<int> answer;
for (int i: T) {
answer.insert(distances[i]);
}
return *answer.begin();
和
int shortest = MAX_INT;
for (int d: distances) {
if( d < shortest ) {
shortest = d;
}
}
return shortest;
修改您的 dijsktra 代碼以在路徑到達 T 節點時停止搜索 - 無需再進一步。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/388162.html