Алгоритм Дейкстры для матриц

Question

Я пытался реализовать алгоритм Дейкстры в C++ 11 для работы с матрицами произвольного размера. В частности, меня интересует решение 83 вопроса о Project Euler.

Кажется, что я всегда столкнулся с ситуацией, когда все узлы, соседствующие с текущим узлом, уже были посещены, что, если я правильно понял алгоритм, никогда не должно происходить.

Я пытался прокрутить в отладчике, и я перечитывал код несколько раз, но я понятия не имею, где я ошибаюсь.

Вот что я сделал до сих пор:

#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 * намного эффективнее, чем этот наивный подход, но то, что я только что описал, более чем достаточно эффективно для решения проблемы.