时间戳

首页 > 解决方案 > Djikstra 的实现似乎与理论复杂性不匹配

c++ - Djikstra 的实现似乎与理论复杂性不匹配

问题描述

我正在实现另一个 Djikstra 的最短路径算法。我已经在较小的数据集上运行了它，据我所知它做得很好。

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

在此处输入图像描述

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

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

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

代码：

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();
}

标签： c++mathgraphics3dgraph-theory

解决方案

把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 });
}

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

推荐阅读