图论 - 单源最短路径(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算法可以求解带权有向图上某个点到其余点的最短路径距离,不支持负权边。
时间复杂度:朴素法的时间复杂度为,加上堆优化以后时间复杂度为。
原理
Dijkstra的流程如下:(白点——未确定最短路径的点 黑点——已确定最短路径的点)
- 初始化dis[src] = 0,其余结点的值为INF。
- 找一个dis值最小的白点x,把x变成黑点。
- 遍历x的所有出边(x,y,z),若dis[x] + z < dis[y],则更新dis[y]。
- 如果所有点都成为黑点,结束,否则跳到2。
正确性:当所有边长都是非负数的时候,全局最小值不可能再被其他结点更新。所以在第2步中找出的白点x必然满足dis[x]是起点到x的最短路径。我们不断选择全局最小值进行标记和拓展,最终可以得到起点到每个结点的最短路径长度。
代码
#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
上一篇: 机器学习算法举例,简明公式及代码
下一篇: SCI投稿后不同状态详解
推荐阅读
-
[单源最短路+路径还原]城市交通路网 HUSTOJ2813
-
【洛谷】P1821 [USACO07FEB] Cow Party S(单源最短路)
-
Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例
-
图论 - 单源最短路径(SPFA)
-
c/c++ 图的最短路径 Dijkstra(迪杰斯特拉)算法
-
Python使用Dijkstra算法实现求解图中最短路径距离问题详解
-
洛谷P4779 【模板】单源最短路径(标准版)
-
python实现Dijkstra算法的最短路径问题
-
图的五种求最短路径算法(Dijkstra、堆优化Dijstra、Bellmon-Ford、SPFA、Floyd-Warshall)
-
PHP实现的迪科斯彻(Dijkstra)最短路径算法实例