C++实现邻接表Dijkstra算法 |21xrx.com

C++实现邻接表Dijkstra算法

2023-06-25 11:31:20 深夜i 12 0

C++ 邻接表 Dijkstra算法图最短路径

Dijkstra算法是一个经典的单源最短路径算法，常用于解决带权重的图问题。邻接表是一种常见的图表示方法，它由多个链表组成，每个链表代表一个节点和它所连的所有边。邻接表在使用Dijkstra算法时可以大大提高效率。本文将介绍如何使用C++实现邻接表Dijkstra算法。

步骤:

1. 定义节点和边的结构体

为了方便操作，我们需要定义节点和边的结构体。节点结构体需要包括一个节点标识和一个指向邻接链表头的指针。边结构体需要包括一个终点节点、一条边的权重以及一个指向下一条边的指针。

2. 初始化邻接表

邻接表可以通过链表实现，在初始化时需要为每个节点创建一个链表头。在邻接表中插入边时，可以通过遍历链表找到对应的节点，然后在该节点的链表中插入边。

3. 实现Dijkstra算法

Dijkstra算法需要维护一个距离数组和一个标记数组。距离数组记录源点到各个节点的最短距离，标记数组记录每个节点是否已经被访问过。

Dijkstra算法的核心是不断地找到距离源点最近的未访问节点，并更新该节点的距离。更新距离时需要考虑两个因素：当前节点的距离和经过当前节点到达终点的距离。具体来说，需要将当前节点的距离加上当前边的权重，得到经过当前节点到达终点的距离，然后判断该距离是否小于当前终点的距离，如果是则更新终点的距离。

4. 输出结果

Dijkstra算法结束后，距离数组中存储的即为源点到各个节点的最短距离。可以依次输出每个节点的距离即可。

示例代码:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 10010;
const int INF = 1e9;
struct Edge
  int to;
struct Node {
  int u, d;
  bool operator<(const Node &x) const
    return d > x.d;
  
};
int head[MAXN], dist[MAXN], vis[MAXN], edgeCnt;
Edge edges[MAXN * 2];
void addEdge(int u, int v, int w) {
  edges[++edgeCnt].to = v;
  edges[edgeCnt].w = w;
  edges[edgeCnt].next = head[u];
  head[u] = edgeCnt;
}
void dijkstra(int s) {
  priority_queue<Node> pq;
  pq.push((Node) s);
  dist[s] = 0;
  while (!pq.empty()) {
    Node node = pq.top();
    pq.pop();
    int u = node.u;
    if (vis[u])
      continue;
    
    vis[u] = 1;
    for (int i = head[u]; i; i = edges[i].next) {
      int v = edges[i].to;
      if (dist[v] > dist[u] + edges[i].w) {
        dist[v] = dist[u] + edges[i].w;
        pq.push((Node) {v, dist[v]});
      }
    }
  }
}
int main() {
  int n, m, s, u, v, w;
  cin >> n >> m >> s;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v >> w;
    addEdge(u, v, w);
  }
  fill(dist + 1, dist + n + 1, INF);
  dijkstra(s);
  for (int i = 1; i <= n; i++) {
    cout << (dist[i] == INF ? -1 : dist[i]) << endl;
  }
  return 0;
}

总结:

邻接表Dijkstra算法是解决带权重的图问题的重要算法之一。相比于邻接矩阵，使用邻接表可以节省空间，同时在查找节点相邻边时时间复杂度更低。在实际应用中，需要注意邻接表的创建和常用操作的实现方式，以及Dijkstra算法的基本思想和实现细节。

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

下一篇: C++数学计算库：高效实用的解决方案

评论区

相似文章