【笔记】数据结构与算法之Dijkstra（堆优化版）
适用于稀疏的边复杂度O（mlogn），比起昨天朴素版的Dijkstra的O（n^2）快不少
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
public class Main {
private static int N= 1000010;
static int n,m;
static PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{return a - b;});//堆
static int idx = 1;
static int [] h = new int,ne = new int,e = new int, w = new int;
// distance 距离
static int [] dist = new int;
//statue判断当前的点是不是最终确定的最短点
staticboolean [] st = new boolean;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] s = bf.readLine().split(" ");
// n个点m条边
n = Integer.parseInt(s);
m = Integer.parseInt(s);
Arrays.fill(h,-1);
for (int i = 0; i < m; i++) {
String []re = bf.readLine().split(" ");
//分别是第一条边和第二条边
int a = Integer.parseInt(re);
int b = Integer.parseInt(re);
//距离
int c = Integer.parseInt(re);
add(a,b,c);
}
System.out.println(dijkstra());
}
static void add(int a, int b, int c){
//当前的idx的element是b
e = b;
//当前的idx的权重是c
w = c;
//当前的idx的next是head
ne = h;
h = idx++;
}
private static int dijkstra() {
//初始化
Arrays.fill(dist, 0x3f3f3f3f);
// 第一个点到自己的距离是0
dist = 0;
//1 to itself distance
pq.add(new int[]{1,0});
while (!pq.isEmpty()){
int [] cur = pq.poll();
int node = cur;
int distance = cur;
//如果存在的就直接continue
if (st){
continue;
}
st = true;
//从h开始
for(int i = h;i!=-1;i = ne){
int j = e;
int curDistance = distance+w;
if (dist>curDistance){
dist = curDistance;
//大的dist
pq.add(new int[]{j,dist});
}
}
}
//4个3f如果不等于0x3f3f3f3f说明找到了 return dist 否则return -1；
if(dist!=0x3f3f3f3f)return dist;
return -1;
}
}
在新标签打开所有链接复制所有链接URL复制所有链接URL（反向）复制所有链接标题 + URL复制所有链接标题 + URL (MD)复制所有链接标题 + URL (BBS)复制所有链接标题 + URL (筛选)复制所有链接标题 + URL (设置复制格式)在新标签页打开所有图片链接在一个标签页显示所有图片链接
复选框 - 选中
复选框 - 取消
复选框 - 反选
单选框 - 选中
单选框 - 取消
特殊单选框 - 选中 楼主请问下有java算法的教程吗 你要同意我就开一个悬赏贴给你
还有就是我想问一下， 学算法主要应用在那些领域，学了算法之后是不是有一个质的提升 Rainsup 发表于 2021-1-1 11:53
楼主请问下有java算法的教程吗 你要同意我就开一个悬赏贴给你
还有就是我想问一下， 学算法主要 ...
1.算法教程：这个东西肯定是有的，因为我不确定哪些是优质的教程，暂且不做推荐；且算法无关语言，是一种思想，我学的算法很多都不是用java写的，例如有c、c++和Python，经过理解再转为java代码的。
2.算法的目的：我只是觉得这个东西很好玩，然后呢我本身也是学计算机的，学习计算机相关的内容也是我的兴趣所在，至于算法用在用在哪些领域，就比如图这个算法吧，地图软件就是使用图的知识，求最短路，或者步行距离最短，还有飞机中转次数最少（没有直达） 不错学习了
页:
[1]