c++ - 矩阵的 Dijkstra 算法

Question

我一直在尝试在 C++11 中实现 Dijkstra 算法以处理任意大小的矩阵。具体来说，我有兴趣解决有关欧拉计划的第 83 题。

我似乎总是遇到这样一种情况，即与当前节点相邻的每个节点都已被访问过，如果我正确理解算法，这种情况永远不会发生。

我试过在调试器中四处寻找，并且我已经多次重新阅读代码，但我不知道我哪里出错了。

这是我到目前为止所做的:

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <set>
#include <tuple>
#include <cstdint>
#include <cinttypes>

typedef std::tuple<size_t, size_t> Index;

std::ostream& operator<<(std::ostream& os, Index i)
{
    os << "(" << std::get<0>(i) << ", " << std::get<1>(i) << ")";
    return os;
}

template<typename T>
class Matrix
{
public:
    Matrix(size_t i, size_t j):
        n(i),
        m(j),
        xs(i * j)
    {}

    Matrix(size_t n, size_t m, const std::string& path):
        n(n),
        m(m),
        xs(n * m)
    {
        std::ifstream mat_in {path};
        char c;
        for (size_t i = 0; i < n; ++i) {
            for (size_t j = 0; j < m - 1; ++j) {
                mat_in >> (*this)(i,j);
                mat_in >> c;
            }
            mat_in >> (*this)(i,m - 1);
        }
    }

    T& operator()(size_t i, size_t j)
    {
        return xs[n * i + j];
    }

    T& operator()(Index i)
    {
        return xs[n * std::get<0>(i) + std::get<1>(i)];
    }

    T operator()(Index i) const
    {
        return xs[n * std::get<0>(i) + std::get<1>(i)];
    }

    std::vector<Index> surrounding(Index ind) const
    {
        size_t i = std::get<0>(ind);
        size_t j = std::get<1>(ind);
        std::vector<Index> is;
        if (i > 0)
            is.push_back(Index(i - 1, j));
        if (i < n - 1)
            is.push_back(Index(i + 1, j));
        if (j > 0)
            is.push_back(Index(i, j - 1));
        if (j < m - 1)
            is.push_back(Index(i, j + 1));
        return is;
    }

    size_t rows() const { return n; }
    size_t cols() const { return m; }

private:
    size_t n;
    size_t m;
    std::vector<T> xs;
};

/* Finds the minimum sum of the weights of the nodes along a path from 1,1 to n,m using Dijkstra's algorithm modified for matrices */
int64_t shortest_path(const Matrix<int>& m)
{
    Index origin(0,0);
    Index current { m.rows() - 1, m.cols() - 1 };
    Matrix<int64_t> nodes(m.rows(), m.cols());
    std::set<Index> in_path;
    for (size_t i = 0; i < m.rows(); ++i)
        for (size_t j = 0; j < m.cols(); ++j)
            nodes(i,j) = INTMAX_MAX;
    nodes(current) = m(current);
    while (1) {
        auto is = m.surrounding(current);
        Index next = origin;
        for (auto i : is) {
            if (in_path.find(i) == in_path.end()) {
                nodes(i) = std::min(nodes(i), nodes(current) + m(i));
                if (nodes(i) < nodes(next))
                    next = i;
            }
        }
        in_path.insert(current);
        current = next;
        if (current == origin)
            return nodes(current);
    }
}

int64_t at(const Matrix<int64_t>& m, const Index& i) { return m(i); }
int at(const Matrix<int>& m, const Index& i) { return m(i); }

int main()
{
    Matrix<int> m(80,80,"mat.txt");
    printf("%" PRIi64 "\n", shortest_path(m));
    return 0;
}

Answer 1

你没有正确理解算法。没有什么能阻止你陷入死胡同。只要还有其他您尚未探索的选项，就将其标记为死胡同并继续前进。

顺便说一句，我同意评论员的说法，他们认为您使解决方案过于复杂了。创建一个“到这里的成本”矩阵并有一个点队列来探索路径就足够了。将总成本矩阵初始化为 NOT_VISITED 的值，-1 会起作用。对于每个点，您都会查看邻居。如果邻居尚未访问过，或者您只是找到了更便宜的路径，则调整成本矩阵并将该点添加到队列中。

继续前进，直到队列为空。然后您就可以保证在任何地方都以最低的成本。

A* 比这种朴素的方法更有效，但我刚才描述的方法足以解决问题。