查询图中的最短路径算法

Question

我有一个加权无向图。它的顶点是两个集合的一部分——S 和 T。首先，输入边。然后指定哪些顶点是 T 集的一部分（其余顶点是 S 集的一部分）。然后是 q 个查询。对于每个查询（由一个源顶点组成），程序必须打印指定源顶点和集合 T 的任何顶点之间的最短路径。
我使用 Dijkstra 算法实现了程序。我为源顶点上的每个查询调用它（dijkstra returns 源和所有其他顶点之间的距离），然后 return 这些数字中的最小值。

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 方法，它直接覆盖了起始邻接矩阵，因为我认为该方法只会被调用一次，然后每次查询只会找到矩阵源行中的最小元素。这次超时更糟。

是否有特定的算法可以在最短路径上进行高效查询？我怎样才能改进我的算法？

Answer 1

这似乎没有必要

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 节点时停止在路径上搜索 - 无需进一步。

Answer 2

您可以反转所有边并找到从 T 的集合（运行 Dijkstra 从所有 T 顶点一起）到某个顶点 S 的最短路径。并预先计算到每个 S 的所有距离并回答查询O(1).

Answer 3

所以，原来问题需要这样解决，只计算一次结果，而不是像我之前那样每次查询都计算一次。解决方案是添加一个假顶点，它连接到 T 集中的所有顶点，并且每条边的权重为零。然后，你必须做 std::vector<int> distances = graph.dijkstra(this fake edge); 并且每个查询的答案是 distances[query].

查询图中的最短路径算法

Shortest path algorithm in graph for queries

c++

algorithm

graph

dijkstra

shortest-path