如何用C++实现有向加权图的Dijkstra算法[封闭式]。

Question

封闭. 这个问题需要更多 集中. 目前不接受回答。

---

想要改进这个问题？ 请通过以下方式更新问题，使其只关注一个问题。编辑本帖.

封闭 5天前.

改进这个问题

会简单明了的说一下。如果需要，我也会尽快把代码贴出来。

我的问题是什么？

我只是不明白如何用C++实现Dijkstra算法来寻找加权有向图的最短路径。

我都试过什么？

我一直在看视频，看教程。遗憾的是这个科目希望我理解，但实际上并没有教你如何在代码中实现，而是展示了其中的步骤。我对C++比较陌生，这个科目的很多同学都是这样，但他们并没有真正去了解如何实现某些方面的代码。

非常感谢任何帮助

Answer 1

首先要注意，经典的Dijkstra算法需要一个优先级队列，队列中的优先级为 decrease_priority() 操作，但在标准库中却没有这样的操作。std::priority_queue 标准库中没有这样的操作。你可以实现Dijkstra算法的一个变体的懒惰删除，它不使用 decrease_priority(). 这种算法的运行时间略有不同，见 这个问题 了解详情。

最简单的实现可能是这样的。

template<typename T>
using min_priority_queue = std::priority_queue<T, 
    std::vector<T>, std::greater<T>>;

auto dijkstra(const graph& g, std::size_t source) {
    std::vector<int> distances(g.size(), std::numeric_limits<int>::max());
    distances[source] = 0;

    min_priority_queue<std::pair<int, std::size_t>> pq;
    pq.emplace(0, source);

    while (!pq.empty()) {
        const auto [distance, vertex] = pq.top();
        pq.pop();

        if (distance > distances[vertex])
            continue;

        const auto relax = [&](std::size_t neighbour, int weight) {
            const auto new_distance = distance + weight;
            if (new_distance < distances[neighbour]) {
                distances[neighbour] = new_distance;
                pq.emplace(new_distance, neighbour);
            }
        };

        g.for_each_edge(vertex, relax);
    }

    return distances;
}

这里 graph 是一个简单的图类。图形顶点是由 0 到 g.size() - 1和 g.for_each_edge(vertex, relax) 调用一个函数 relax(neighbour, weight) 对于每个相邻的顶点 neighbour 连接到顶点的 vertex 挨边 weight.