C ++中的Dijktras算法

Question

我正在尝试在网格图中找到任何两个给定点之间的最小成本路径，如main()函数所示，其中每个网格都有与其行驶相关的成本。我只能从矩阵的（0,0）到（10,10）获得最小路径。我如何进一步修改代码以在任何两点之间获得最低成本。任何帮助或指示将不胜感激。

{
    int x, y;
    int distance;
    cell(int x, int y, int distance)
        : x(x)
        , y(y)
        , distance(distance)
    {
    }
};

bool operator<(const cell& a, const cell& b)
{
    if (a.distance == b.distance) {
        if (a.x != b.x)
            return (a.x < b.x);
        else
            return (a.y < b.y);
    }
    return (a.distance < b.distance);
}

bool isInsideGrid(int i, int j)
{
    return (i >= 0 && i < COL && j >= 0 && j < ROW);
}

int shortest(int grid[ROW][COL], int row, int col)
{
    int dis[row][col];

    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            dis[i][j] = INT_MAX;
    cout << INT_MAX;
    int dx[] = { -1, 0, 1, 0 };
    int dy[] = { 0, 1, 0, -1 };

    set<cell> st;

    st.insert(cell(0, 0, 0));

    dis[0][0] = grid[0][0];

    while (!st.empty()) {

        cell k = *st.begin();
        st.erase(st.begin());

        // looping through all neighbours
        for (int i = 0; i < 4; i++) {
            int x = k.x + dx[i];
            int y = k.y + dy[i];

            if (!isInsideGrid(x, y))
                continue;

            if (dis[x][y] > dis[k.x][k.y] + grid[x][y]) {

                if (dis[x][y] != INT_MAX)
                    st.erase(st.find(cell(x, y, dis[x][y])));

                dis[x][y] = dis[k.x][k.y] + grid[x][y];
                st.insert(cell(x, y, dis[x][y]));
            }
        }
    }

    for (int i = 0; i < row; i++, cout << endl)
        for (int j = 0; j < col; j++)
            cout << dis[i][j] << " ";

    return dis[row - 1][col - 1];
}

int main()
{
    int grid[ROW][COL] = {
        2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
        2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
        2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
        2, 2, 2, 5, 5, 5, 5, 2, 2, 2,
        2, 2, 2, 5, 5, 5, 5, 2, 2, 2,
        2, 2, 2, 5, 5, 5, 5, 2, 2, 2,
        2, 2, 2, 5, 5, 5, 5, 2, 2, 2,
        2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
        2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
        2, 2, 2, 2, 2, 2, 2, 2, 2, 2,

    };

    cout << shortest(grid, 10, 10) << endl;
    return 0;
}

Answer 1

我如何进一步修改代码，以在任何两点之间获得最小的成本。任何帮助或指示将不胜感激。谢谢！

您可以做的是转换此：

  cout << shortest(grid, 10,10 ) << endl;

进入用户，它将采用两个坐标，例如end_x和end_y。然后，您可以按原样将这些参数传递到函数中。

因此，最终的代码可能类似于：

cin>>end_x>>end_y;
cout<< shortest(grid, end_x, end_y) << endl;

如果要在系统中找到每个点的输出，那么您可能希望对其进行for循环。如果我们假设所有点对都存在的10x10网格，则代码可能如下所示：

for(int i = 0;i < 10;i++)
{  for(int j = 0;j < 10;j++)
      cout<< shortest(grid, i, j) << endl;
}

我希望这可以解决您的问题：）

PS：我没有检查算法，所以我认为它是正确的。

最佳