Dijkstra求解单源最短路径
2024-09-03 18:57:06
Dijkstra(迪杰斯特拉)单源最短路径算法
Dijkstra思想
Dijkstra是一种求单源最短路径的算法。
Dijkstra仅仅适用于非负权图,但是时间复杂度十分优秀。
Dijkstra算法主要思想是:
主要思想是,将结点分成两个集合:已确定最短路长度的,未确定的。
一开始第一个集合里只有节点V。
然后重复这些操作:
1.对那些刚刚被加入第一个集合的结点的所有出边执行松弛操作。
2.从第二个集合中,选取一个最短路长度最小的结点,移到第一个集合中。
用暴力算法的时间复杂度是Ο(n2+m) = Ο(n2)。
用小根堆优化的时间复杂度是Ο(m log n)。
还有一些复杂的实现Dijkstra算法,比如说:priority_queue(时间复杂度:Ο(m log m))
ZKW线段树(时间复杂度:O(m log n + n) = Ο(m log n))
fibonacci堆(时间复杂度:Ο(n log n + m))
感兴趣的OIer想具体了解这几种方法,可以上网查一查,这里不多赘述。
Dijkstra暴力法代码
// by kyrence
#include <bits/stdc++.h>
using namespace std; const int S = 3e3 + , INF = 0x3f3f3f3f;
int adj[S][S], dist[S], n, m;
bool vis[S]; void dijkstra() {
memset(dist, INF, sizeof(dist));
memset(vis, , sizeof(vis));
dist[] = ;
for (int i = ; i < n; i++) {
int x = ;
for (int j = ; j <= n; j++) //找到未标记的节点中dist最小的节点对其它节点进行更新
if (!vis[j] && (!x || dist[j] < dist[x]))
x = j;
vis[x] = ;
for (int j = ; j <= n; j++) //更新其它节点的最短路
dist[j] = min(dist[j], dist[x] + adj[x][j]);
}
} int main() {
memset(adj, INF, sizeof(adj)); //构建邻接矩阵
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) adj[i][i] = ; //节点V到节点V的距离为0
for (int i = ; i <= m; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
adj[x][y] = z; //有向图
//adj[x][y] = adj[y][x] = z; 无向图
}
dijkstra(); //dijkstra暴力法求解单源最短路径
for (int i = ; i <= n; i++)
printf("%d\n", (dist[i] == INF ? - : dist[i])); //-1代表节点1到节点i没有路径
return ;
}
Dijkstra小根堆优化代码
// by kyrence
#include <bits/stdc++.h>
using namespace std; const int N = 1e5 + , M = 1e6 + , INF = 0x3f3f3f3f;
int head[N], ver[M], edge[M], Next[M], dist[N]; //构建邻接表
int n, m, tot;
bool vis[N];
priority_queue<pair<int, int> > q; //小根堆第一项取负,使小根堆变成大根堆
//在不使用小顶优先队列情况下取负将小根堆变成大根堆加速优先队列,常见的加速技巧 void add(int x, int y, int data) { //邻接表存储图
ver[++tot] = y;
edge[tot] = data;
Next[tot] = head[x];
head[x] = tot;
} void dijkstra() {
memset(dist, INF, sizeof(dist));
memset(vis, , sizeof(vis));
dist[] = ; q.push(make_pair(, ));
while (!q.empty()) {
int u = q.top().second; q.pop(); //找到未访问节点中dist最小的节点
if (vis[u]) continue; //如果节点u已经访问则忽略
vis[u] = ;
for (int i = head[u]; i; i = Next[i]) { //邻接表访问出边
int y = ver[i], z = edge[i];
if (dist[y] > dist[u] + z) {
dist[y] = dist[u] + z; //更新节点
q.push(make_pair(-dist[y], y)); //取负值,加速小根堆
}
}
}
} int main() {
scanf("%d%d", &n, &m);
for (int i = ; i <= m; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z); //无向图
//add(x, y, z); add(y, x, z); 有向图
}
dijkstra(); //dijkstra小根堆优化求解单源最短路径
for (int i = ; i <= n; i++)
printf("%d\n", (dist[i] == INF ? - : dist[i])); //-1代表节点1到节点i没有路径
return ;
}
力荐使用小根堆优化,代码简洁直观易懂,空间小,时间复杂度优。
最新文章
- PHP Excel 下载数据,并分页下载
- #iOS问题记录# 关于UITableViewcel的分割线去掉问题
- js跨域解决方案(转载)
- (转)WCF开发框架形成之旅---WCF的几种寄宿方式
- C#正则提取HTML中img的url值
- N个任务掌握java系列之统计一篇文章中单词出现的次数
- IIs 网站应用程序与虚拟目录的区别及高级应用说明(文件分布式存储方案)
- Android的电源管理框架
- New : HTML5 中的新标签
- 关于变量 Objects...objects 和Object[] objects的区别
- Do you know how many stuff inside your Google Account?
- 【转】构建高性能WEB站点之 吞吐率、吞吐量、TPS、性能测试
- mysql查询正在执行的sql
- 客户端ip获取蹲坑启示: 不要侥幸
- svn&#160;checkout&#160;实用小技巧
- springboot学习章节代码-spring基础
- 字符串算法hash
- 1.C#知识点:值类型和引用类型
- nginx配置php时fastcgi_pass参数问题
- 解决 android.support.v7.widget.GridLayout 使用 xmlns:app 出现 error 的问题