C++实现邻接矩阵最短路径 |21xrx.com

C++实现邻接矩阵最短路径

2023-07-05 11:39:05 深夜i -- --

C++ 邻接矩阵最短路径

在计算机领域中，最短路径是一类常见的问题，也是一种重要的算法。其中，邻接矩阵最短路径算法是其中的一种。本文将介绍如何使用 C++ 实现邻接矩阵最短路径算法。

邻接矩阵是一个方阵，其中每个元素表示两个顶点之间边的权重。在最短路径算法中，我们把邻接矩阵用于计算两个节点之间的最短距离。下面是一个示例邻接矩阵：


int adj_matrix[5][5] = {
   10,
   1,
  3,
  INT_MAX,
   8
};

在上述矩阵中，我们表示了一个由五个节点组成的图。在这个图中，节点之间的连接关系被赋予了一个权重值，其中 `INT_MAX` 表示两个节点之间没有边相连。

邻接矩阵最短路径算法的核心是 Dijkstra 算法。Dijkstra 算法是一种贪心算法，其中从源节点开始，对每个节点进行检测，并计算出到达该节点的最小路径。该算法用一个数组来记录从源节点到其他所有节点的距离，在经过每次迭代后，它会选择下一个节点，该节点距离源节点的距离最短。在本算法中，我们使用一个辅助数组来记录每个节点的最短路径。

下面是我们使用 C++ 实现邻接矩阵最短路径算法的示例代码：


#include<bits/stdc++.h>
using namespace std;
const int V = 5;
int adj_matrix[V][V] = {
  0,
   0,
  3,
  INT_MAX,
   2
};
int shortest_path(int start, int dest) {
  int dist[V];
  bool visited[V];
  for (int i = 0; i < V; i++) {
    dist[i] = INT_MAX;
    visited[i] = false;
  }
  dist[start] = 0;
  for (int i = 0; i < V-1; i++) {
    int u = -1;
    for (int j = 0; j < V; j++) {
      if (!visited[j] && (u == -1 || dist[j] < dist[u]))
        u = j;
      
    }
    visited[u] = true;
    for (int v = 0; v < V; v++) {
      if (adj_matrix[u][v] != INT_MAX) {
        int new_dist = dist[u] + adj_matrix[u][v];
        if (new_dist < dist[v]) {
          dist[v] = new_dist;
        }
      }
    }
  }
  return dist[dest];
}
int main() {
  cout<<shortest_path(0, 4)<<endl;
  return 0;
}

在上述代码中，`shortest_path()` 函数是算法的核心部分。该函数接受两个参数，分别为起点和终点，返回最短路径的长度。运行示例代码，输出结果为 `9`。换句话说，从起点 `0` 到终点 `4` 的最短路径长度为 `9`。可以将此结果与我们之前对应邻接矩阵的矩阵元素值进行比较，验证结果的正确性。

通过本文，我们了解了如何使用 C++ 实现邻接矩阵最短路径算法。此算法的时间复杂度为 $O(V^2)$，其中 $V$ 是节点数量。虽然该算法的时间复杂度可能比其他更高级的算法慢，但由于它是理解最短路径算法的基础，因此它仍然是我们需要掌握的重要内容。

上一篇: idea打包java可执行jar包

下一篇: C++实现栈：一种基本数据结构

评论区

()

相似文章