图的邻接矩阵，求最短路径的方法

最短路径可以使用Dijkstra算法或者Floyd算法来实现。

Dijkstra算法：
该算法用于求单源最短路径。首先将原点到其他节点的距离设置为无穷大，然后将原点的距离设置为0。对于原点相邻的节点，更新其距离为原点到该节点的距离。接着从未处理的距离最短的节点开始，更新其相邻节点的距离。不断重复这个过程，直到所有节点的距离都更新完成。

Floyd算法：
该算法用于求全源最短路径。它通过动态规划的方式，从任意两点之间的距离来计算任意两点之间的最短路径。首先将任意两点之间的距离设置为邻接矩阵中的权值，如果两点不相邻，则其距离为无穷大。接着对于每个节点，依次尝试将其加入最短路径中，看是否能够缩短路径。如果可以，则更新距离矩阵。最终，矩阵中每个元素存储的就是对应节点之间的最短路径距离。

相关问题

有向图邻接矩阵求最短路径

有向图的邻接矩阵可以被用来求解最短路径，其中迪杰斯特拉算法是一个常用的方法。迪杰斯特拉算法用于解决单源最短路径问题，即从一个顶点出发，求解到其他所有顶点的最短路径。

首先，我们可以使用邻接矩阵来存储有向图的边的关系。邻接矩阵是一个二维数组，数组的行和列分别代表图中的顶点，而数组中的元素代表了顶点之间的边的权值。如果两个顶点之间存在边，则对应位置的元素值为边的权值；如果两个顶点之间不存在边，则对应位置的元素值为无穷大或者一个很大的数。

在迪杰斯特拉算法中，首先需要初始化一个距离数组，用来存储从源顶点到其他顶点的当前最短路径长度。然后，从源顶点开始，不断更新距离数组，直到找到所有顶点的最短路径。

具体步骤如下：
1. 初始化距离数组，将源顶点的距离设为0，将其他顶点的距离设为无穷大。
2. 选择一个顶点作为当前顶点，标记为已访问。
3. 更新当前顶点的邻居顶点的距离。如果通过当前顶点到达邻居顶点的路径长度小于邻居顶点当前的最短路径长度，则更新邻居顶点的最短路径长度。
4. 重复步骤3，直到所有顶点都被访问过或者找到最短路径。
5. 根据距离数组，可以得到从源顶点到其他顶点的最短路径。

在求解最短路径时，需要记录每个顶点的前驱顶点，以便在最后打印路径时能够回溯到源顶点。可以使用一个前驱数组来存储每个顶点的前驱顶点。

需要注意的是，迪杰斯特拉算法要求图中的权值不能为负值，因为负权边可能导致算法陷入死循环。

因此，使用邻接矩阵和迪杰斯特拉算法可以求解有向图的最短路径。通过初始化距离数组、更新距离数组和记录前驱顶点，可以得到从源顶点到其他顶点的最短路径。<span class="em">1</span><span class="em">2</span><span class="em">3</span>

邻接矩阵求最短路径c++

邻接矩阵求最短路径的算法通常使用 Dijkstra 算法或 Floyd 算法。

1. Dijkstra 算法

Dijkstra 算法是一种单源最短路径算法，其基本思想是从源节点开始，不断扩展最短路径，直到到达目标节点为止。具体步骤如下：

（1）初始化：将源节点 s 到所有节点的距离初始化为无穷大，将源节点 s 到自身的距离初始化为 0。

（2）遍历：从源节点 s 开始，按照距离从小到大的顺序遍历所有节点，并更新它们到源节点 s 的距离。

（3）更新：对于当前节点 u 的所有邻居节点 v，如果 u 到源节点 s 的距离加上 u 到 v 的距离小于当前已知的 v 到源节点 s 的距离，则更新 v 的距离。

（4）重复：重复步骤（2）和（3）直到遍历完所有节点或者找到目标节点。

C++ 代码实现：

const int INF = 0x3f3f3f3f;  // 无穷大
int n;                       // 节点数
int G[MAX][MAX];             // 邻接矩阵
int d[MAX];                  // s 到各点的距离
bool vis[MAX];               // 标记是否已确定最短距离

void Dijkstra(int s) {
    memset(vis, 0, sizeof(vis));
    fill(d, d + n, INF);
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && (u == -1 || d[j] < d[u])) {
                u = j;
            }
        }
        vis[u] = true;
        for (int v = 0; v < n; v++) {
            if (!vis[v] && G[u][v] != INF && d[u] + G[u][v] < d[v]) {
                d[v] = d[u] + G[u][v];
            }
        }
    }
}

2. Floyd 算法

Floyd 算法是一种多源最短路径算法，其基本思想是通过中间节点的遍历，不断缩小节点间的距离，直到得到最终的最短路径。具体步骤如下：

（1）初始化：将邻接矩阵 G 初始化为节点间的距离。

（2）遍历：从节点 i 到节点 j 的最短路径可能经过节点 k，因此遍历所有可能的 k 值，更新 i 到 j 的最短路径。

C++ 代码实现：

const int INF = 0x3f3f3f3f;  // 无穷大
int n;                       // 节点数
int G[MAX][MAX];             // 邻接矩阵

void Floyd() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
            }
        }
    }
}