算法分析
1、什么是spfa算法?
$\quad$SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环。SPFA一般情况复杂度是$O(m)$ 最坏情况下复杂度和朴素 Bellman-Ford 相同,为$ O(nm)$。
bellman-ford算法操作如下:
for n次
$\quad$for 所有边 a,b,w (松弛操作)
$\quad$$\quad$dist[b] = min(dist[b],back[a] + w)
$\quad$$\quad$spfa算法对第二行中所有边进行松弛操作进行了优化,原因是在bellman—ford算法中,即使该点的最短距离尚未更新过,但还是需要用尚未更新过的值去更新其他点,由此可知,该操作是不必要的,我们只需要找到更新过的值去更新其他点即可。
2、spfa算法步骤
queue <– 1
while queue 不为空
$\quad$$\quad$ (1) t <– 队头
$\quad$$\quad$$\quad$ queue.pop()
$\quad$$\quad$ (2)用 t 更新所有出边 t –> b,权值为w
$\quad$$\quad$$\quad$ queue <– b (若该点被更新过,则拿该点更新其他点)
时间复杂度 一般:$O(m)$ 最坏:$O(nm)$
n为点数,m为边数
3、spfa也能解决权值为正的图的最短距离问题,且一般情况下比Dijkstra算法还好
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N = 100010;
static int n;
static int m;
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int[] w = new int[N];
static int idx = 0;
static int[] dist = new int[N];
static boolean[] st = new boolean[N]; //标记是否在队列中
static int INF = 0x3f3f3f3f;
public static void add(int a,int b,int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
public static int spfa()
{
Arrays.fill(dist, INF);
Queue<Integer> queue = new LinkedList<Integer>();
dist[1] = 0;
queue.add(1);
st[1] = true;//标记1号点在队列中
while(!queue.isEmpty())
{
int t = queue.poll();
st[t] = false;
for(int i = h[t];i != -1;i = ne[i])
{
int j = e[i];//获取点编号
//若该点被更新过,则加入队列中
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
//判断该点是否已经在队列中
if(!st[j])
{
queue.add(j);
st[j] = true;//标记已加入队列
}
}
}
}
return dist[n];
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] str1 = reader.readLine().split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
Arrays.fill(h, -1);
while(m -- > 0)
{
String[] str2 = reader.readLine().split(" ");
int a = Integer.parseInt(str2[0]);
int b = Integer.parseInt(str2[1]);
int c = Integer.parseInt(str2[2]);
add(a,b,c);
}
int t = spfa();
if(t == 0x3f3f3f3f) System.out.println("impossible");
else System.out.println(t);
}
}
if(!st[j])有啥用?????
st数组的作用:判断当前的点是否已经加入到队列当中了;已经加入队列的结点就不需要反复的把该点加入到队列中了,就算此次还是会更新到源点的距离,那只用更新一下数值而不用加入到队列当中。
来自:https://www.acwing.com/solution/content/9306/
java 使用StreamTokenizer读取数据的话,会更快
楼主 想问个问题 一直不太明白为啥判断按那个点是否进入队列要放在第一个if里面而不是并列
大赞!!
tql
赞一个,但不得不说用java来刷题真的是累死个人哈哈哈哈
习惯就好哈哈
参见大佬~