引理:
图中有多个起点,多个终点,求任意起点到任意终点的最短路问题,如下图所示
注意:虚拟源点的方法:只能求出来的是多个起点到任意终点的一条最短距离(计算出多个起点到终点最短的一条),而不能求出多个起点每个起点到任意终点的最短路距离(后者是floyd
算法)
-
原问题:从每个起点出发,到达任意终点的所有路线的距离的最小值
-
加上虚拟源点之后的问题:从虚拟源点出发,到达任意终点的所有路线的距离的最小值
其中虚拟源点到起点的权值为0
算法分析
-
方法一:通过上述引理,可以转换成求从虚拟源点到终点的的最短路问题
-
方法二:建反向图,从终点开始求到所有点的单源最短路,取每个给定起点的最短长度
代码使用的是方法一
时间复杂度 $O(m)$
SPFA 算法的时间复杂度是 $O(km)$,其中 $k$ 一般情况下是个很小的常数,最坏情况下是 $n$, $n$ 表示总点数,$m$ 表示总边数。因此最坏情况下的复杂度是 $O(nm)$。
参考文献
算法提高课
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 = 1010;
static int M = 21010;
static int n;
static int m;
static int s;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int[] w = new int[M];
static int idx = 0;
static int[] dist = new int[N];
static boolean[] st = new boolean[N];
static int INF = 0x3f3f3f3f;
static void add(int a,int b,int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
static int spfa()
{
Queue<Integer> q = new LinkedList<Integer>();
Arrays.fill(dist, INF);
q.add(0);
dist[0] = 0;
st[0] = true;
while(!q.isEmpty())
{
int t = q.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])
{
q.add(j);
st[j] = true;
}
}
}
}
if(dist[s] == INF) return -1;
return dist[s];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true)
{
String tmp = br.readLine();
if(tmp == null) break;
String[] s1 = tmp.split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
s = Integer.parseInt(s1[2]);
Arrays.fill(h, -1);
idx = 0;
while(m -- > 0)
{
String[] s2 = br.readLine().split(" ");
int a = Integer.parseInt(s2[0]);
int b = Integer.parseInt(s2[1]);
int c = Integer.parseInt(s2[2]);
add(a,b,c);
}
int cnt = Integer.parseInt(br.readLine().trim());
String[] s3 = br.readLine().split(" ");
for(int i = 0;i < cnt;i ++)
{
int b = Integer.parseInt(s3[i]);
add(0,b,0);
}
System.out.println(spfa());
}
}
}
SPFA最坏情况下的复杂度似乎是 $O(nm)$ 不是 $O(km)$ ~
谢谢提醒,已修改