Djikstra 的实现似乎与理论复杂性不符

Question

我正在实施另一个 Djikstra 的最短路径算法。我在小型数据集上使用了运行它，据我所知它做事很好。

目标是使用它来近似网格上的测地线。因此，例如下图中的绿线是连接 2 个红点的测地线的近似值：

该图像中的网格有 409 个顶点和 2304 个边。渐近复杂性将给出： 409 + 2304 * log(409) \大约 14 000 步。

我的算法运行需要 830678 步来计算您看到的解决方案。我知道实际步数与 t 的渐近符号不匹配，但数量级应该更接近。此外，我的算法的运行time 似乎随着输入的增长而稳步增加。例如，对于渐近复杂度预测 30,000 次迭代的输入，算法运行进行数百万次迭代，直到我杀死它（即它可以继续运行）。几乎就好像复杂度是运行超几何级数或指数级。

我想看看我在哪里搞砸了，以至于我得到了正确的输出（测试）但错误运行时间。

代码：

template <typename T>
std::pair<std::vector<uint>, std::vector<double>> Djikstra(
    const std::vector<T>& node_list,
    std::vector<T> (*GetNeighbours)(const T& t),
    uint (*GetId)(const T& t),
    double (*GetDistance)(const T& t1, const T& t2),
    uint start)
{
    std::vector<double> node_distance_map(node_list.size(), std::numeric_limits<double>::max());
    std::vector<uint> node_parent_map(node_list.size());
    std::vector<bool> node_visited_map(node_list.size(), false);

    typedef std::pair<double, uint> NodeInfo;
    std::priority_queue<NodeInfo, std::vector<NodeInfo>, std::greater<NodeInfo>> queue;

    node_distance_map[start] = 0;
    node_parent_map[start] = start;
    queue.push({0, start});

    uint current_node_index = start;
    uint count = 0;
    while(!queue.empty())
    {
        auto[current_distance, current_node_index] = queue.top();
        queue.pop();
        auto current_node = node_list[current_node_index];

        node_visited_map[current_node_index] = true;

        auto neighbours = GetNeighbours(current_node);
        assert(neighbours.size() > 0);
        double shortest_distance = std::numeric_limits<double>::max();
        auto& shortest_neighbour = neighbours[0];
        for(auto& neighbour : neighbours)
        {
            uint neighbour_id = GetId(neighbour);
            // Skip any node that has already been visited
            if(node_visited_map[neighbour_id]) continue;
            double distance = GetDistance(current_node, neighbour);
            double total_distance = distance + current_distance;

            // Overwrite prior distances of the current distance is shorter
            queue.push({total_distance, neighbour_id});
            if(total_distance < node_distance_map[neighbour_id])
            {
                node_parent_map[neighbour_id] = current_node_index;
                node_distance_map[neighbour_id] = total_distance;
            }
        }
        if(count++ % 1'000'000 == 0) std::cout << "At: " << count << std::endl;
    }
    std::cout << "Final: " << count << std::endl;

    return {node_parent_map, node_distance_map};
}

编辑：

这是表示图表的 DS：

struct Node
{
    typedef std::shared_ptr<Node> NodePtr;
    uint id;
    vector<std::shared_ptr<Node>> neighbours;
    Eigen::Vector3d position;
};

std::vector<Node::NodePtr> NodeGetNeighbours(const Node::NodePtr& v)
{
    return v->neighbours;
}

uint NodeGetId(const Node::NodePtr& v)
{
    return v->id;
}

double NodeGetDistance(const Node::NodePtr& v1, const Node::NodePtr& v2)
{
    return (v1->position - v2->position).norm();
}

Answer 1

将 queue.push() 语句放入 if.

if (total_distance < node_distance_map[neighbour_id])
{
    node_parent_map[neighbour_id] = current_node_index;
    node_distance_map[neighbour_id] = total_distance;
    queue.push({ total_distance, neighbour_id });
}

如果不这样做，您仍然会得到正确的答案，但是优先级队列的大小会随着您的操作方式不断增加，因为即使 total_distance >= node_distance_map[neighbour_id] 它仍在推送这个新的 pair .事实上，要实现最快的 Dijkstra 实现，您必须使用 decreasePriority 方法创建一个优先级队列。但是为此，需要知道存储对象的队列中的 index，您希望降低其优先级。这样你就可以保证优先级队列中的节点不会超过 N 个。

Djikstra 的实现似乎与理论复杂性不符

Implementation of Djikstra doesn't seem to match theoretical complexity

c++

math

3d

graphics

graph-theory