C++邻接矩阵迪杰斯特拉算法实现 |21xrx.com

C++邻接矩阵迪杰斯特拉算法实现

2023-07-02 07:10:24 深夜i -- --

C++ 邻接矩阵迪杰斯特拉算法实现

迪杰斯特拉算法是解决单源最短路径的一种经典算法。该算法利用贪心策略每次找到当前节点到其他未访问的节点中距离最短的节点，直到找到目标节点或者所有节点都被访问。在此基础上，我们可以利用邻接矩阵来实现该算法。

邻接矩阵是一种图数据结构，用二维数组表示。其中，每行和每列分别对应图中的一个顶点，如果两个顶点之间存在边，则将相应的数组元素设为边的权值；否则设为无穷大。

实现思路：

1. 初始化距离数组dist和访问标记visited。初始时，距离数组为无穷大，访问标记为false。

2. 从源节点开始，将源节点的距离设为0。

3. 以贪心策略逐步更新dist数组。每次找到未访问节点中距离源节点最短的节点u，并将节点u标记为已访问。

4. 从源节点跨过节点u，更新源节点到其它未访问节点v的距离。如果源节点通过节点u到达节点v的距离比直接到达节点v的距离更小，则更新dist数组。

5. 重复步骤3和4，直到找到目标节点或所有节点都被访问。

代码实现：


void dijkstra(int source, int target, int size, int** graph)
{
  int* dist = new int[size];
  bool* visited = new bool[size];
  // 初始化
  for(int i = 0; i < size; i++) {
    dist[i] = INT_MAX;
    visited[i] = false;
  }
  // 将源节点设为0
  dist[source] = 0;
  // 逐步更新dist数组
  for(int i = 0; i < size-1; i++) {
    int u = minDist(dist, visited, size);
    visited[u] = true;
    // 更新dist数组
    for(int v = 0; v < size; v++) {
      if(!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u]+graph[u][v] < dist[v])
        dist[v] = dist[u] + graph[u][v];
    }
  }
  // 输出结果
  cout << "Shortest distance from source to target: " << dist[target] << endl;
  // 释放内存
  delete[] dist;
  delete[] visited;
}

其中，minDist函数用于找到未访问节点中距离源节点最短的节点。代码如下：


int minDist(int* dist, bool* visited, int size) {
  int min = INT_MAX, minIndex;
  for(int i = 0; i < size; i++) {
    if(!visited[i] && dist[i] <= min) {
      min = dist[i];
      minIndex = i;
    }
  }
  return minIndex;
}

总结：

使用邻接矩阵实现迪杰斯特拉算法可以快速解决单源最短路径问题。在实现过程中，需要注意初始化距离数组和访问标记数组，并考虑如何维护dist数组的更新。此外，应该注意内存泄漏问题，需要在算法结束后释放动态分配的空间。

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

下一篇: 《C++ Primer》中文版电子书

评论区

()

相似文章