邻接矩阵图最短距离c++

邻接矩阵是一种用于表示图的数据结构，其中用二维数组来存储图中每个顶点之间的连接状态。对于最短路径问题，比如计算两点间的最短距离，可以使用Dijkstra算法或Floyd-Warshall算法。

1. Dijkstra算法适用于有向无环图(DAG)或无权图，它通过维护一个优先队列，每次选择当前未访问节点中最短距离的那个节点，并更新与其相邻节点的距离。C++中可以使用`std::priority_queue`实现。

#include <vector>
#include <queue>

int dijkstra(const std::vector<std::vector<int>>& graph, int start) {
    // ... 算法主体，包括初始化距离数组、设置起点距离为0、构建优先队列等
}

2. Floyd-Warshall算法适用于有权图，它通过动态规划的方式遍历每对顶点的所有中间节点，逐步更新所有节点对的最短距离。C++中可以用循环实现：

#include <vector>

void floydWarshall(std::vector<std::vector<int>>& graph) {
    for (size_t k = 0; k < graph.size(); ++k) {
        for (size_t i = 0; i < graph.size(); ++i) {
            for (size_t j = 0; j < graph.size(); ++j) {
                if (graph[i][k] + graph[k][j] < graph[i][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}