没有对角线移动的 Dijkstra 算法

Question

抱歉，如果这个问题有点愚蠢，但我找不到合适的解决方案。我想获得从一个点到另一个点的最短路径。我在互联网上找到了一个代码，但是这个代码给了我对角线的路径，我只需要垂直和水平移动。任何人都可以告诉我我应该改变什么？因为我尝试了几次修改，其中 none 似乎有效。这是代码：

提前致谢。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Cell 
{    
    int x;
    int y;

    public:

        int getx(){ 
            return x; 
        }
        int gety(){ 
            return y; 
        }
        void setx(int x){
            this->x = x;
        }
        void sety(int y){
            this->y = y;
        }
        bool operator==(Cell o) {
            return x==o.x && y==o.y;
        }
        Cell operator=(Cell o) {
            x = o.x; 
            y = o.y; 
            return *this;
        }
        Cell(int x, int y):x(x),y(y){ }
        Cell():x(0),y(0){}
};
vector<Cell> getShortestPath(Cell ori, Cell dest, int array[], int width, int height);

int main()
{
    int ejemplo[] = {
        0,1,0,1,0,0,0,0,        //0: void
        0,1,0,1,0,0,0,0,        //1: obstacle
        0,1,0,1,0,0,0,0,
        0,1,0,1,0,0,0,0,
        0,1,0,1,0,0,0,0,
        0,1,0,1,0,0,0,0,
        0,0,0,1,0,0,0,0,
        0,0,0,0,0,0,0,0};

    vector<Cell> camino= getShortestPath(Cell(2,0),Cell(0,7),ejemplo,8,8);

    for(int i = 0; i < camino.size(); i++) {
        cout << "(" << camino[i].getx() << ", " << camino[i].gety() << ")" << endl;
    }
}

vector<Cell> getShortestPath(Cell ori, Cell dest, int array[], int width, int height)
{
    if ( ori == dest ) 
        return vector<Cell>();

    unsigned int *sizes = new unsigned int[width*height];
    Cell *prev = new Cell[width*height];

    for(int i = 0; i < width*height; i++) {
        sizes[i] = -1; 
        prev[i] = Cell(-1,-1);
    }

    sizes[ori.getx()+ori.gety()*width] = 0;
    prev[ori.getx()+ori.gety()*width] = ori;


    queue<Cell> porVisitar;
    porVisitar.push(ori);

    while(!porVisitar.empty())
    {
        Cell cur = porVisitar.front();
        porVisitar.pop();
        cout << porVisitar.size() << endl;

        for(int i = -1; i < 2; i++)
           for(int j = -1; j < 2; j++)
                if((cur.getx()+j)>=0 && (cur.getx()+j)<width && (cur.gety()+i)>=0 && (cur.gety()+i)<height &&      //is not out of bounds
                 array[(cur.getx()+j)+(cur.gety()+i)*width]==0 &&           //is not an obstable
                 sizes[cur.getx()+cur.gety()*width]+1 < sizes[(cur.getx()+j)+(cur.gety()+i)*width]      //there is not a better path
                ) {
                    sizes[(cur.getx()+j)+(cur.gety()+i)*width]=sizes[cur.getx()+cur.gety()*width]+1;
                    prev[(cur.getx()+j)+(cur.gety()+i)*width]=Cell(cur.getx(),cur.gety());
                    porVisitar.push(Cell(cur.getx()+j,cur.gety()+i));
                }
    }

    if(prev[dest.getx()+dest.gety()*width]==Cell(-1,-1)) 
        return vector<Cell>();

    Cell pp = dest;
    vector<Cell> res(sizes[dest.getx()+dest.gety()*width]+1);

    for(int i = res.size()-1; !(pp == ori); i-- )
    {
         res[i] = pp;
         pp = prev[pp.getx()+pp.gety()*width];
     }

     return res;

Answer 1

考虑子图：

a b c
d N e
f g h

其中 N 是您当前的 node/vertex。将邻居添加到潜在路径列表（或队列，或其他）时，仅添加 b、d、e 和 g。上面的代码添加了a-h.

提示：这发生在嵌套的for循环中。

回答：条件句应该是if((i != -1 && i != 1) || (j != 1 && j != -1)).

没有对角线移动的 Dijkstra 算法

Dijkstra algorithm without diagonal moves

c++

path

dijkstra

path-finding