TOC
前言： 今天做题叒叕把心态给做崩了，本来想给自己放一个小假，但看看距离比赛的天数所剩无几，又想到冷落Blog有一阵子了，最近又学习了最短路的两种算法SPFA和Dijkstra，也在做题中碰了各种壁；决定还是将他整理记录下来吧。学SPFA和Dijkstra我是先看的各个大佬的博客，看了好多大佬的博客就不一一列举了，了解了这两种算法的基本原理及实现流程，再去B站看的一个叫”qscqesze“UP主的视频，最后自己用Java把SPFA和Dijkstra实现了。
SPFA实际上就是用的BFS,Dijkstra用的是优先队列。具体原理网上各位大佬整理的比我详细，我主要贴出我的Java代码和我在用算法实现题目过程中碰到的一些问题。
老规矩，还是用一道普通的题目来体现：(题目来自洛谷)
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入格式
第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。
接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。
输出格式
一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）
输入输出样例
输入 #1
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出 #1
0 2 4 3
涉及到负权图的时候就必须用SPFA，换句话说DijKstra只能在正权图上使用，但SPFA都可以使用。但是有些题会出数据卡SPFA，虽然这样SPFA还是依然好用,Dijkstra还是依然经典。
这道题用两种方法都可以AC，但我在AC的路上也碰到了各种问题，最让我苦恼的是一直报MLE，我试过了如链式前向星等各种存图方式，最终都以MLE告终，最后我终于找到了他：
SPFA代码：
import java.io.*;
import java.util.*;
public class Main {
//存图和最短路径一个数组即可
public static NODE[] nodes;
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
int N = (int)in.nval;
in.nextToken();
int M = (int)in.nval;
in.nextToken();
int S = (int)in.nval;
nodes = new NODE[10010];
for (int i = 1; i < 10010; i++) {
//记得初始化，否则报空指针
nodes[i] = new NODE(i);
}
for (int i = 0; i < M; i++) {
in.nextToken();
int from = (int)in.nval;
in.nextToken();
int to = (int)in.nval;
in.nextToken();
int d = (int)in.nval;
//存图
int[] tmp = new int[2];
tmp[0] = to;
tmp[1] = d;
nodes[from].others.add(tmp);
}
nodes[S].ifUse = true;
nodes[S].length = 0;
Queue<NODE> queue = new ArrayDeque<>();
queue.offer(nodes[S]);
//SPFA主要逻辑部分
while (!queue.isEmpty()) {
int now = queue.poll().index;
//从队列中取出，变true为false
nodes[now].ifUse = false;
for (int i = 0; i < nodes[now].others.size(); i++) {
int to = nodes[now].others.get(i)[0];
int d = nodes[now].others.get(i)[1];
//判断路径是否更短，更短则更新
if (nodes[to].length > nodes[now].length + d) {
nodes[to].length = nodes[now].length + d;
//再把当前节点放进队列
if (nodes[to].ifUse) {
continue;
}
nodes[to].ifUse = true;
queue.offer(nodes[to]);
}
}
}
for (int i = 1; i <= N; i++) {
if (nodes[i].length == 9999999) {
out.print("2147483647 ");
}else {
out.print(nodes[i].length+" ");
}
}
out.println();
out.flush();
}
}
}
class NODE {
//判断是否在队列中
boolean ifUse;
//点的编号
int index;
//起点到这个点的最短路
int length;
//存放从这个点到其它点的信息
List<int[]> others;
//初始化
public NODE(int index) {
this.index = index;
length = 9999999;
others = new ArrayList<>();
ifUse = false;
}
}
Dijkstra代码：
import java.io.*;
import java.util.*;
public class Main {
public static Dj[] djs;
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
int N = (int)in.nval;
in.nextToken();
int M = (int)in.nval;
in.nextToken();
int S = (int)in.nval;
djs = new Dj[100010];
for (int i = 1; i <= N; i++) {
djs[i] = new Dj(i);
}
for (int i = 0; i < M; i++) {
in.nextToken();
int from = (int)in.nval;
in.nextToken();
int to = (int)in.nval;
in.nextToken();
int d = (int)in.nval;
int[] tmp = new int[2];
tmp[0] = to;
tmp[1] = d;
djs[from].others.add(tmp);
}
//以上代码跟SPFA基本一样
//用到优先队列
PriorityQueue<Dj> queue = new PriorityQueue<>();
djs[S].length = 0;
queue.offer(djs[S]);
//Dijkstra主要逻辑代码
while (!queue.isEmpty()) {
int now = queue.poll().index;
for (int i = 0; i < djs[now].others.size(); i++) {
int to = djs[now].others.get(i)[0];
int d = djs[now].others.get(i)[1];
if (djs[to].length > djs[now].length+ d) {
djs[to].length = djs[now].length+ d;
queue.offer(djs[to]);
}
}
}
for (int i = 1; i <= N; i++) {
if (djs[i].length == 9999999) {
out.print("2147483647 ");
}else {
System.out.print(djs[i].length+" ");
}
}
out.println();
out.flush();
}
}
}
class Dj implements Comparable<Dj>{
int index;
int length;
List<int[]> others;
public Dj(int index) {
this.index = index;
length = 9999999;
others = new ArrayList<>();
}
@Override
public int compareTo(Dj o) {
return new Integer(-this.length).compareTo(-o.length);
}
}
以上题解不断更新，如有大佬看出问题，我必虚心请教及时更改！
「真诚赞赏，手留余香」
水的一匹Lu的Blog
真诚赞赏，手留余香
使用微信扫描二维码完成支付
