欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

图论 - 单源最短路径(Dijkstra)

程序员文章站 2022-06-26 17:56:57
文章目录定义原理代码定义Dijkstra算法可以求解带权有向图上某个点到其余点的最短路径距离,不支持负权边。时间复杂度:朴素法的时间复杂度为O(N2)O(N^2)O(N2),加上堆优化以后时间复杂度为O((N+M)log2(N))O((N + M)log_2(N))O((N+M)log2​(N))。原理Dijkstra的流程如下:(白点——未确定最短路径的点 黑点——已确定最短路径的点)初始化dis[src] = 0,其余结点的值为INF。找一个dis值最小的白点x,把x变成黑点。遍历x...

文章目录

定义

Dijkstra算法可以求解带权有向图上某个点到其余点的最短路径距离,不支持负权边

时间复杂度:朴素法的时间复杂度为O(N2)O(N^2),加上堆优化以后时间复杂度为O((N+M)log2(N))O((N + M)log_2(N))

原理

Dijkstra的流程如下:(白点——未确定最短路径的点 黑点——已确定最短路径的点)

  1. 初始化dis[src] = 0,其余结点的值为INF。
  2. 找一个dis值最小的白点x,把x变成黑点。
  3. 遍历x的所有出边(x,y,z),若dis[x] + z < dis[y],则更新dis[y]。
  4. 如果所有点都成为黑点,结束,否则跳到2。

正确性:当所有边长都是非负数的时候,全局最小值不可能再被其他结点更新。所以在第2步中找出的白点x必然满足dis[x]是起点到x的最短路径。我们不断选择全局最小值进行标记和拓展,最终可以得到起点到每个结点的最短路径长度。

代码

洛谷P4779

#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <map>
#include <set>
#include <cstring>
#include <climits>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

int n, m, s;
const int MAXN = 100005;
const int MAXM = 200005;
int head[MAXN];
struct Edge {
    int dest, weight, next;
} edges[MAXM];
int edges_cnt = 0;
int dis[MAXN];
bool visited[MAXN];

void addEdge(int src, int dest, int weight) {
    ++edges_cnt;
    edges[edges_cnt].dest = dest;
    edges[edges_cnt].weight = weight;
    edges[edges_cnt].next = head[src];
    head[src] = edges_cnt;
}

struct QNode {
    int node, dis;

    bool operator<(const QNode& other) const {
        return dis > other.dis;
    }
};

void dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    memset(visited, 0, sizeof(visited));
    priority_queue<QNode> pq;
    pq.push({s, 0});
    dis[s] = 0;
    while (!pq.empty()) {
        QNode top = pq.top();
        pq.pop();
        if (!visited[top.node]) {
            visited[top.node] = true;
            for (int i = head[top.node]; i; i = edges[i].next) {
                int dest = edges[i].dest;
                int weight = edges[i].weight;
                if (dis[top.node] + weight < dis[dest]) {
                    dis[dest] = dis[top.node] + weight;
                    if (!visited[dest]) {
                        pq.push({dest, dis[dest]});
                    }
                }
            }
        }
    }
}

int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d%d%d", &n, &m, &s);
    while (m--) {
        int src, dest, weight;
        scanf("%d%d%d", &src, &dest, &weight);
        addEdge(src, dest, weight);
    }
    dijkstra();
    for (int node = 1; node <= n; ++node) {
        printf("%d ", dis[node]);
    }
    putchar('\n');

    return 0;
}

本文地址:https://blog.csdn.net/hcmdghv587/article/details/107599837