21xrx.com
2024-12-23 00:48:54 Monday
登录
文章检索 我的文章 写文章
Dijkstra算法C++模板
2023-06-30 03:37:47 深夜i     --     --
Dijkstra算法 C++ 模板

Dijkstra算法是一种用于图论问题中求解最短路径的经典算法。该算法的主要思想是从起始点开始,将所有点分为两个集合,一个集合是已经求得最短路径的点的集合,另一个集合是未求得最短路径的点的集合。每次从未求得最短路径的点中选择距离起始点最近的点加入已求得最短路径的点的集合中,并且更新与该点相邻的点到起点的距离。重复这个过程直到所有点都加入到已求得最短路径的点的集合中,最终得到起始点到其他节点的最短路径。

下面是Dijkstra算法的C++模板:


const int INF = 0x3f3f3f3f;

struct Edge

  int to;

  int cost;

;

vector<Edge> G[MAXN];

int dist[MAXN];

bool vis[MAXN];

void dijkstra(int s, int n) {

  memset(vis, false, sizeof(vis));

  memset(dist, INF, sizeof(dist));

  dist[s] = 0;

  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;

  que.push(make_pair(0, s));

  while (!que.empty()) {

    pair<int, int> p = que.top();

    que.pop();

    int v = p.second;

    if (vis[v]) continue;

    vis[v] = true;

    for (int i = 0; i < G[v].size(); i++) {

      Edge e = G[v][i];

      if (dist[e.to] > dist[v] + e.cost) {

        dist[e.to] = dist[v] + e.cost;

        que.push(make_pair(dist[e.to], e.to));

      }

    }

  }

}

该模板使用了一个结构体Edge来存储边信息,其中to表示终点,cost表示边权值。G数组用于存储图的信息,其下标表示该点的编号,对应的存储的是从该点出发的边的信息。dist数组存储从起始点到每个节点的最短距离,vis数组表示该点是否已经加入已求得最短路径的点的集合中。

该模板中除了常数INF用于初始化dist数组外,其余的值都可以根据实际情况进行调整和修改。

总的来说,Dijkstra算法是一种十分经典的算法,应用广泛。通过本篇文章的C++模板,我们可以更好地理解该算法的实现过程和细节,进而将其运用到实际场景中去。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复