2. 矩阵左上角到右下角的最短路径c++

在C++中，计算矩阵左上角到右下角的最短路径通常使用动态规划算法中的Floyd-Warshall法或者Dijkstra算法。这里我们以Floyd-Warshall算法为例，因为它可以同时处理所有点之间的最短路径，而不仅仅是两个特定点。

Floyd-Warshall算法的工作原理是通过迭代所有的中间节点，更新每对节点间的最短路径。以下是基本步骤：

1. 初始化一个二维数组`dist`，其中`dist[i][j]`表示从节点i到节点j的最短距离，如果它们不在同一行，则设为无穷大（通常用INT_MAX或者很大的正数）。

2. 对于矩阵中的每个节点k，检查是否有比当前`dist[i][j]`更短的路径：`dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`。这个过程会更新了所有节点对之间的最短路径。

3. 重复步骤2，直到所有的`dist`值不再改变。这意味着已经找到了从左上角到右下角经过所有节点的最短路径。

下面是简单的C++代码示例：

#include <bits/stdc++.h>
using namespace std;

#define INF INT_MAX

int floydWarshall(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            if (i != k && matrix[i][k] != INF) {
                for (int j = 0; j < n; ++j) {
                    if (matrix[j][k] != INF && matrix[i][j] > matrix[i][k] + matrix[k][j]) {
                        matrix[i][j] = matrix[i][k] + matrix[k][j];
                    }
                }
            }
        }
    }
    return matrix[0][n - 1]; // 返回从左上角到右下角的最短距离
}

// 使用示例
vector<vector<int>> createMatrix(int size) {
    vector<vector<int>> matrix(size, vector<int>(size));
    // 初始化矩阵...
    return matrix;
}

int main() {
    int size;
    cin >> size;
    vector<vector<int>> matrix = createMatrix(size);
    int shortestPath = floydWarshall(matrix);
    cout << "Shortest path from top-left to bottom-right is: " << shortestPath << endl;
    return 0;
}