dijkstra算法的板子

Dijkstra算法的板子如下：

1. 初始化：将起点s到各个点的距离dist[s]初始化为0，将其它点的距离dist[i]初始化为无穷大，将所有点的标记visited[i]初始化为false。

2. 循环n次，每次找到一个距离起点s最近的未标记点u，将其标记visited[u]设为true。

3. 对于所有与u相邻的未标记点v，如果dist[u]+w(u,v)<dist[v]，则更新dist[v]=dist[u]+w(u,v)。

4. 重复步骤2和3，直到所有点都被标记为止。

5. 最终得到起点s到各个点的最短距离dist[i]。

希望这个回答对你有所帮助。

相关问题

dijkstra算法板子

Dijkstra算法是一种用于解决单源最短路径问题的贪心算法。它的基本思想是从起点开始，每次寻找当前最短路径的节点并加入到已处理节点的集合中，然后更新与该节点相邻的节点的距离。这个过程不断重复，直到所有节点都被处理。

以下是Dijkstra算法的C++实现：

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;

typedef pair<int, int> PII; // 存储节点编号和距离的pair

const int N = 100010; // 图中最多有100010个节点
int n, m; // n表示节点数，m表示边数
int h[N], e[N], w[N], ne[N], idx; // 邻接表存储图
int dist[N]; // 存储起点到每个节点的最短距离
bool st[N]; // 存储每个节点是否已经加入已处理节点的集合中

void add(int a, int b, int c) // 添加一条边a->b，权重为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra(int start, int end)
{
    memset(dist, 0x3f, sizeof dist); // 将起点到每个节点的距离初始化为无穷大
    dist[start] = 0; // 起点到自己的距离为0

    priority_queue<PII, vector<PII>, greater<PII>> q; // 小根堆存储节点编号和距离的pair
    q.push({0, start}); // 将起点加入小根堆中

    while (q.size()) // 只要小根堆不为空，就继续搜索
    {
        auto t = q.top();
        q.pop();

        int ver = t.second, distance = t.first; // 取出距离起点最近的节点及其距离

        if (st[ver]) continue; // 如果该节点已经在已处理节点的集合中，就直接跳过

        st[ver] = true; // 将该节点加入已处理节点的集合中

        for (int i = h[ver]; i != -1; i = ne[i]) // 枚举该节点的所有出边
        {
            int j = e[i]; // 取出这条边的终点编号
            if (dist[j] > distance + w[i]) // 如果从起点到j的路径长度可以被更新
            {
                dist[j] = distance + w[i]; // 更新路径长度
                q.push({dist[j], j}); // 将更新后的节点加入小根堆中
            }
        }
    }

    if (dist[end] == 0x3f3f3f3f) return -1; // 如果起点无法到达终点，就返回-1
    return dist[end]; // 返回起点到终点的最短距离
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    int start, end;
    cin >> start >> end;

    cout << dijkstra(start, end) << endl;

    return 0;
}

在这个实现中，我们使用了邻接表来存储图，使用了小根堆来维护未处理节点集合中距离起点最近的节点。在实现过程中，我们需要注意以下几点：

1. 将起点到每个节点的距离初始化为无穷大（这里使用了0x3f3f3f3f）；
2. 每次取出小根堆中距离起点最近的节点时，需要判断该节点是否已经在已处理节点的集合中；
3. 每次更新节点的距离时，需要将更新后的节点加入小根堆中。

dijkstra算法的板子代码

以下是dijkstra算法的板子代码：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1005;

struct Edge {
    int to, w;
    Edge(int to, int w) : to(to), w(w) {}
};

vector<Edge> G[MAXN];
int d[MAXN];
bool vis[MAXN];

void dijkstra(int s) {
    memset(d, INF, sizeof(d));
    memset(vis, false, sizeof(vis));
    d[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, s));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].to;
            int w = G[u][i].w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push(make_pair(d[v], v));
            }
        }
    }
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(Edge(v, w));
    }
    dijkstra(s);
    for (int i = 1; i <= n; i++) {
        if (d[i] == INF) cout << "INF ";
        else cout << d[i] << " ";
    }
    cout << endl;
    return 0;
}

希望能对你有所帮助！